Dynamic Programming

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   DP = recursion + a notebook. Solve each small question once, store it, and build bigger answers from stored ones.

   #1
2. ↯use it when

   "Count the ways", "min/max cost", "is it possible" — with a choice at each step and a brute-force recursion that repeats the same arguments.

   #2
3. { }template

   State (what dp[i] means) → transition → base cases → fill order → answer cell. Write these 5 lines as comments first.

   #3
4. O( )cost

   Time = states × work per state. Stairs: n × O(1). LCS: m·n × O(1). LIS: n × O(n). Knapsack: n·W — pseudo-polynomial.

   #4
5. { }template

   Memo: int[] memo filled with −1, check → compute → store. Table: new int[n + 1], loop up from the base cases.

   #5
6. ✦pro tip

   Only the last 1–2 cells or rows are read? Keep prev2/prev1 or prev/cur rows: O(n) → O(1), O(m·n) → O(n).

   #6
7. !trap

   0/1 knapsack in 1D: loop capacity DOWN. Going up lets an item be reused — that's unbounded knapsack.

   #7
8. !trap

   Coins outside → combinations (LC 518). Target outside → orderings (LC 377). Swap the loops and you change the answer.

   #8
9. !trap

   Integer.MAX_VALUE + 1 wraps negative: use amount + 1 as infinity. Use −1 (not 0) for "not computed" when 0 is a real answer.

   #9
10. ✦pro tip

    Stuck? Write the brute-force recursion first. Its changing parameters ARE the DP state.

    #10

Shaky on a card? Open the chapter or flip its recall cards.