Dynamic programming is not black magic
Dynamic programming is framed not as “black magic” but as a systematic way to turn exponential-time recursive problems into efficient algorithms by identifying overlapping subproblems and caching their results. Commenters debate how best to teach and understand it—top‑down recursion plus memoization vs. bottom‑up table filling—and clarify that memoization, optimization, and related terms are often conflated or poorly explained. The thread also touches on the technique’s origin and naming, its relationship to algorithms like Dijkstra’s, and where DP actually shows up in practice, from interview problems to bioinformatics and combinatorial counting.
Definitions and conceptual framing
- DP described as a method for solving multistage or discrete‑time decision/optimization problems: define a value function where each state’s value depends on optimal values of “smaller” states.
- Several commenters emphasize “optimal substructure” and overlapping subproblems as the real core, not code-level tricks.
- Others reduce it to: recursion + memoization + (good) decomposition of the problem, noting that the hardest part is finding the right recurrence.
Memoization vs dynamic programming
- Common question: “Is DP just memoization?”
- One side: memoization is a general caching technique; DP is systematic memoization over a structured subproblem space, often with a DAG interpretation and bottom‑up order.
- Others argue that practically, DP problems can be taught and implemented as “start with recursion, add memoization (top‑down), then convert to bottom‑up table and optimize space.”
- Examples like Fibonacci, edit distance, LCS, knapsack, subset sum, and stock-trading problems are used to illustrate top‑down vs bottom‑up, and when you can shrink tables to a few rows or constants.
Teaching and difficulty
- Many feel DP is often taught poorly: jumping directly to tables makes it feel like a puzzle or “black magic.”
- Advocated teaching pattern:
- get a correct (possibly exponential) recursive solution;
- add memoization;
- turn it into an iterative/tabular solution;
- optimize memory if possible.
- Disagreement over best mental model: “smart caching” vs more abstract “DAG of subproblems / dynamic optimization.” One side prioritizes accessibility, the other conceptual rigor.
Algorithms and applications mentioned
- Classic DP problems: longest common subsequence/substring, line wrap, coin change, knapsack, subset sum, matrix chain multiplication, edit distance, longest path in DAGs, weighted independent set on a path, shortest paths on DAGs, sequence alignment (Needleman–Wunsch, Smith–Waterman).
- Real‑world/legacy uses: Go position counting, bioinformatics, Emacs screen redisplay, puzzle/level generation, Advent of Code solutions.
- Debate over whether Dijkstra’s algorithm should be classified as DP; some say yes via a dynamic‑programming optimality condition and label‑correcting view, others say its state exploration pattern differs from standard DP tabulation.
Naming, history, and perception
- Multiple comments recount the historical origin: “programming” in the optimization sense; “dynamic” chosen for political/marketing reasons.
- Some complain the term is misleading or overly broad; suggestions include more descriptive names like “tabulation” or “array memoization.”
Usage in practice and interviews
- Mixed reports on practical use: some rarely need DP beyond contests/AoC; others note it quietly underlies many library algorithms and helps avoid accidental quadratic behavior.
- Strong sentiment that in interviews, alternative correct approaches (e.g., genetic algorithms) should be accepted, but also pushback that randomized/heuristic methods differ fundamentally from deterministic DP with clear time bounds.
Other discussion threads
- Brief meta‑discussion on what counts as science (in a tangent about psychoanalysis) and on how concepts like “optimization” and “bootstrap” are named and perceived.