Divide-and-conquer is not the shallow idea of "break the big problem into smaller ones." It requires that subproblems be structurally isomorphic to the original AND relatively independent. Only when both hold does recursion actually reduce complexity. Otherwise you've just moved code around without saving any work.
Non-trivial: (1) the merge step decides everything. The Master Theorem makes it formal — if merge cost ≥ subproblem cost, divide-and-conquer doesn't pay. This is why "split-then-combine" sounds appealing but often delivers no speedup. (2) The dominant failure mode is "pseudo-divide": subproblems share state, call back into each other, look split but are tightly coupled. Diagnostic: can two subproblems be solved by two people in two rooms without speaking? If no, the boundary is wrong. (3) Structurally isomorphic to the Buddhist deconstruction of self: what looks like one "big problem" is an aggregate; see it as a small number of independent strands and difficulty drops an order of magnitude.
Practice: before dividing, answer two questions — "How expensive is my merge?" and "How many hidden dependencies cross the subproblem boundary?" If either is high, stop dividing and pick a different strategy.
Merge sort, O(n log n): split the array in half, recurse, then linearly merge. Merge cost O(n) < subproblem cost → the Master Theorem yields O(n log n). MapReduce is the engineering-scale incarnation — Google indexed petabytes by ensuring "map is independent, reduce is cheap." The moment reduce becomes expensive (cross-shard joins, complex aggregations), the divide-advantage evaporates and the framework turns into a performance killer.
(1) Engineering: split an "AI system overhaul" into data layer / model layer / application layer / evaluation layer. If those four layers need a weekly 3-hour sync meeting to move forward, that's pseudo-divide — the boundary is wrong. True divide = the four teams take interface contracts and run independently for 90 days. (2) Learning a new field: split "introduction to quantum mechanics" into math basics / physical intuition / experimental facts / philosophical interpretations. The strands are relatively independent (interpretations don't change the math) and the merge is cheap (draw one concept map at the end). (3) The earliest symptom of pseudo-divide is meeting growth — if cross-subteam meetings climb exponentially, the subproblems aren't independent enough. Redraw boundaries; don't schedule more syncs.
The surface story is "trade space for time" — that's the appearance. The real requirement is that the problem simultaneously exhibits overlapping subproblems (the same computation is needed many times) AND optimal substructure (the global optimum can be assembled from subproblem optima). Miss either and DP degenerates into ordinary recursion or greedy.
Non-trivial: (1) everything hinges on state definition. Pick the wrong state and no clever transition can save you — you'll hit state-space explosion, going from O(n²) to O(n⁴). (2) Top-down memoization vs bottom-up tabulation have different mental shapes — the former is "cache on demand," lazy but close to natural thinking; the latter is "systematically fill the table," memory-hungry but more controllable. Beginners graduate from the first to the second. (3) Non-trivial observation: most life problems are not DP problems — they lack optimal substructure (you don't keep revisiting identical states; the environment drifts). Misapplying DP to life means polishing answers to past states that are no longer relevant, locking yourself into path dependence. (4) Structurally isomorphic to the Bellman equation in reinforcement learning: intelligence = learning which subproblems are worth memoizing and which are noise that shouldn't be cached.
Practice: before coding, ask "what's the dimensionality of my state space?" Each new dimension grows the table exponentially. If state exceeds 3 dimensions, compress or abstract first, then DP.
0-1 knapsack: naive recursion is O(2ⁿ) and becomes uncomputable at 30 items. DP compresses it to O(n·W) via a 2D table (item index × remaining capacity) — milliseconds. The same subproblem "best value using items 1..i with capacity w" is hit millions of times; without memoization you re-climb the same tree over and over. Reinforcement learning's Q-learning is DP extended to stochastic environments — the Q-table is noisy memoization.
(1) AI agent engineering: every LLM call thinks from scratch = no memoization, exponential token waste. Add a "decision cache" layer to your agent — record "for similar past queries, what did I reason and conclude?" — collapsing repeat queries from O(K tokens) to O(1) lookup. Prerequisite: your queries actually have overlapping subproblems. (2) Personal decision lookup table: write recurring life decisions (take this project? attend this meeting?) as "criteria + past precedents" — next time a similar situation arises, look up, not re-derive, and decision fatigue collapses. (3) But beware: when the problem distribution drifts, the DP table expires — your child enters a new developmental stage, the AI paradigm shifts, the industry reorganizes — old tables instantly become stale. Healthy practice is periodic "rebuild" and dating each cache entry with an expiry.
Greedy = pick the locally best move at every step. Tempting because it's simple, fast, and "often good enough." But it's strictly optimal only on the rare problems with matroid structure. Most real problems are not matroids — greedy will reliably ship you to a local-optimum trap, with the far-off global peak forever invisible.
Non-trivial: (1) the mountain metaphor: greedy is "always step uphill," and you finish at the nearest hilltop to your starting point. The hilltop is not the highest peak in the range. (2) Engineering escapes from local optima come in three families — simulated annealing (allow occasional descent), beam search (keep K candidates), random restart (greedy from many starts). All three share the same move: tolerate temporary worsening. (3) The inverse cognitive trap from sunk-cost: sunk-cost is reluctance to let go of the past; greedy local optima is blindness to the far — one is rear-view blindness, the other is far-view blindness. (4) Structurally isomorphic to the Buddhist concept of avidyā (ignorance): blinded by the brightest nearby lamp, you can't see the global terrain. Awareness = switching from "best at each step" to "best overall" as the optimization target.
Dijkstra's shortest path is greedy AND globally optimal — because shortest-path on graphs has matroid structure (a confirmed shortest distance can't get shorter). But greedy on 0-1 knapsack fails — "pack the highest value-per-weight item first" misses the optimum at certain capacities. Coin change: greedy works for [1, 5, 10, 25] cents, but on [1, 3, 4] coins to make 6 it returns 4+1+1 (three coins) instead of optimal 3+3 (two coins). Whether greedy works depends on the problem's skeleton, not on your intuition.
(1) Career choice: jumping every year to "the next job with the biggest raise" is classic greedy. But the career function has no matroid structure — three years in management dulls technical depth; three years in pure technical work closes the management track. Step-wise local optimality locks you onto a small hilltop. (2) Antidote: deliberately "simulate-anneal" — accept one descent (a temporary pay cut, a hard pivot into AI, going abroad, founding something) to buy the option of jumping out of the local optimum. (3) Parenting: every day choosing "the path that triggers the least fuss" (more screen time, more toys) is greedy. You'll grind into a local optimum where the child permanently avoids hard things. The short-term uncomfortable "do the hard task together" move is the parenting version of simulated annealing. (4) Non-trivial AI corollary: a large language model is itself a giant greedy machine — token-by-token sampling of the most probable next move — which is precisely why beam search, temperature, and long-horizon planning exist as counter-greedy mechanisms.
When a problem is provably NP-hard, the optimum is unreachable — not "try harder" unreachable, but "the universe will end first" unreachable. You must trade optimality for tractability. But how you trade matters: good heuristics carry approximation guarantees (e.g., 1.5-approximate TSP); bad heuristics are guesses dressed up as method.
Non-trivial: (1) the closer a heuristic function tracks the true optimum, the cheaper the search. A*'s efficiency lives or dies by it — a bad heuristic degrades A* into BFS; a perfect heuristic linearizes the search. (2) Heuristic strength = depth of structural understanding of the problem. Counter-intuitive: heuristics aren't shortcuts around knowledge, they are compressed knowledge. (3) Structurally isomorphic to "intuition": human experience-based intuition is a heuristic function learned over a lifetime by the brain. But beware — a good heuristic is valid only inside its training distribution; out-of-distribution (new domain, new context), it silently fails. This is why senior experts crash on cross-domain moves. (4) Monte Carlo Tree Search (MCTS) + neural value function = the strongest general-purpose heuristic of our era (AlphaGo compressed the 10^170 Go search space into a playable game). And this is the lifeline of LLMs too: they are essentially "approximators that learned vast heuristics from human language" — strong inside familiar distributions, failing in the sparse long tail.
Practice: in a new domain, first admit your heuristic is empty and do honest slow search; only after enough data has accumulated should you trust the fast take. Skip this step and you'll exponentially amplify a wrong heuristic.
The Traveling Salesman Problem is NP-hard — 50 cities means 50! routes, more than the universe's age can enumerate. Christofides' algorithm gives a 1.5-approximation guarantee (route length ≤ 1.5 × optimum), good enough in practice. AlphaGo doesn't enumerate Go: it's MCTS (heuristic sampling) + a learned value network (the heuristic function), turning the intractable into the tractable. Modern SAT solvers handle billion-variable formulas via stacked heuristics (DPLL, CDCL) that suppress exponential blow-up.
(1) AI agent planning: asking an LLM for "the complete optimal plan" is shoving an NP-hard problem into the context window — the result is hallucination collage. The better move is to hand it a set of good heuristic functions ("list your assumptions first," "ask 'why' at each step," "prune immediately on failure") and let it run heuristic search instead of brute force. (2) Major personal decisions: when the problem is too large to enumerate ("will I be satisfied 30 years from now?"), stop hunting for the optimum and switch to "approximately acceptable + preserve optionality" — add a 1.5× buffer around heuristic conclusions to absorb bias. (3) Parenting and education: abandon "the optimal education path" — it's NP-hard and the distribution will shift (the world in 10 years is unrecognizable). Design a small set of good heuristics ("prioritize meta-abilities," "preserve optionality," "periodically retrain your own heuristic function"). (4) Meta-insight: "experience" is essentially a heuristic function — measure experience not by years, but by approximation ratio and applicable distribution. Actively retraining when crossing domains is how senior people stay effective.