Skip to content

Dynamic Programming Thinking

Problems with overlapping subproblems and optimal substructure can be solved efficiently by storing solutions to subproblems, transforming exponential recursive solutions into polynomial ones.

Tension Addressed

Time vs. Space (trades space for time via memoization)

Recognizable As

Memoization patterns, bottom-up table filling, shortest path algorithms, sequence alignment, resource allocation with constraints, any recursive solution with repeated subproblem computation

Canonical Sources

Bellman, Dynamic Programming (1957); Bellman, The Theory of Dynamic Programming (1954)

Transfers To

Financial planning, operations research, bioinformatics, natural language processing, game theory, control systems

Sub-concepts: - Optimal substructure: Optimal solution contains optimal solutions to subproblems - Overlapping subproblems: Same subproblems recur across different decompositions - Memoization vs. tabulation: Top-down caching vs. bottom-up construction