Topic 17 of 20
Recursion plus memory: define a state, write the recurrence, fill the table.
Dynamic programming (DP) solves problems made of overlapping subproblems by solving each subproblem once and storing the answer. If your backtracking solution keeps recomputing the same calls, DP is the fix. A DP solution has three parts: a state (what does dp[i] mean, in one precise sentence?), a recurrence (how is dp[i] built from smaller states?), and base cases.
There are two ways to implement it. Top-down (memoisation) is your recursive solution plus a cache, and it is usually the easiest place to start. Bottom-up (tabulation) fills an array in order. It avoids recursion limits and often lets you shrink memory to a few variables. In interviews, starting top-down and then converting to bottom-up is a strong way to show understanding.
In 1D DP the state is a single index or amount. Learn the families here (Fibonacci-style steps, take-or-skip, 0/1 and unbounded knapsack, longest increasing subsequence, segmentation) and most new DP problems will turn out to be one of them in disguise.
The 'hello world' of DP.
Adds costs to the stair recurrence.
Rolling variables for O(1) space.
Building each row from the previous one.
The canonical take-or-skip recurrence.
Handle a circle by solving two linear cases.
Reduces to House Robber after bucketing values.
Counting decodings with validity checks; asked often at Meta.
Minimum coins, the classic unbounded knapsack.
Counting ordered sequences; contrast it with Coin Change II.
Minimum squares, with a BFS alternative.
Subset sum with a boolean 0/1 knapsack.
Reducing ± signs to a subset-sum count.
Track both max and min because negatives flip signs.
Circular max = total − minimum subarray.
Segmentation DP; one of the most-asked DP problems.
O(n²) DP and the O(n log n) patience-sorting method.
Expand around centres, or interval DP.
Counting all palindromic substrings.
Memoised enumeration of all segmentations.
Sort cleverly, then run LIS.
Weighted interval scheduling; asked frequently at Google and Amazon.
State design with a hash map of reachable jumps.