Dynamic Programming
Recognise when a problem has optimal substructure and overlapping subproblems, define the state precisely, write the recurrence and base cases, and fill states in dependency order, top-down with a cache or bottom-up with a table.
Key points
- 1
Define dp[i] (or dp[i][j]) in words first; the recurrence, base cases and answer location all follow from that definition.
- 2
Memoization recurses lazily and caches results; tabulation loops in dependency order and avoids Python's recursion limit (1000 by default).
- 3
Coin change: coin loop outside counts combinations, amount loop outside counts ordered sequences. Min-coin tables must start at infinity, not 0.
- 4
In a 1-D knapsack table, iterate capacity downward for 0/1 knapsack and upward for unbounded knapsack.
- 5
LIS in O(n log n) keeps the smallest tail per length with bisect_left; its length is the answer, but the array is not itself a subsequence.
- 6
Complexity is states × work per state: LCS O(mn), knapsack O(nW) (pseudo-polynomial), bitmask TSP O(n²·2ⁿ).
- 7
Rolling arrays cut memory when a state depends on a bounded window, but you lose the full table needed to reconstruct the solution.
Common traps
Iterating capacity upward in a 1-D 0/1 knapsack silently reuses items and over-counts the value.
Initialising a min-coin table with zeros makes every answer 0, because min() never raises a cell.
Maximum product subarray must track the minimum product too; a negative number turns the smallest product into the largest.
Read the source
Test yourself on Dynamic Programming
Ten questions, with the answer and explanation after each one.