23.02Intermediate7 topics18 min7 interactive animations

DP workflow

The six-step DP workflow: define the state, define the transition, set the base cases, choose the evaluation order, extract the answer, then analyse complexity and optimise space.

Learning goals

Follow a fixed sequence of steps for any dynamic programming problem
Write the state definition as a complete sentence
Choose base cases that make the transition correct at the boundary
Pick an evaluation order that computes dependencies first
Extract the answer from the right cell and compute the cost from states and transitions
Reduce space when only a few past states are needed

Prerequisites

Recognizing dynamic programming problems

Experienced people solve dynamic programming problems by following the same checklist every time. Following it prevents the two most common failures: a vague state and a forgotten base case.

23.02.1

Define state

Step one: write the state as a **sentence in words**, including what each index means and whether it is inclusive. 'dp[i] is the maximum loot from the first i houses' is a definition. 'dp[i] is the best at i' is not.

The sentence settles most later questions: the array size, the base case (what is dp for zero houses?), the answer (dp[n]) and whether the transition has the information it needs. In the house-robber animation the table header reads exactly such a sentence, and each cell is one value of it.

Java

1// state: best[i] = the largest total loot from the first i houses (house 1 .. house i), no two adjacent
2// answer: best[n]
3static int[] houseRobberTable(int[] value) {
4    int n = value.length;
5    int[] best = new int[n + 1];
6    for (int i = 1; i <= n; i++) {
7        best[i] = Math.max(best[i - 1], (i >= 2 ? best[i - 2] : 0) + value[i - 1]);
8    }
9    return best;
10}

House robber: take it or skip it

Interactive · edit the input

house money

2h1

7h2

9h3

3h4

1h5

dp[i] = best from the first i houses

0none

2rob h1

?i=2

?i=3

?i=4

?i=5

Setup

For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).

Step 1 / 6

Java

1static int rob(int[] a) {                             // no two adjacent houses
2    int n = a.length; int[] dp = new int[n + 1];      // dp[i] = best loot from the first i houses
3    dp[1] = a[0];
4    for (int i = 2; i <= n; i++)
5        dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);   // skip house i, or rob it and use the best before the neighbour
6    return dp[n];
7}

Live state

houses

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L3	houses=5	For the first i houses, the best loot either skips house i (best of the first i−1) or robs it (its money plus the best of the first i−2, because the neighbour is off limits).
2	L5	i=2 skip=2 rob=7 dp[i]=7	House 2: skipping keeps 2; robbing gives dp[0] + 7 = 7. Best 7 (rob it).
3	L5	i=3 skip=7 rob=11 dp[i]=11	House 3: skipping keeps 7; robbing gives dp[1] + 9 = 11. Best 11 (rob it).
4	L5	i=4 skip=11 rob=10 dp[i]=11	House 4: skipping keeps 11; robbing gives dp[2] + 3 = 10. Best 11 (skip it).
5	L5	i=5 skip=11 rob=12 dp[i]=12	House 5: skipping keeps 11; robbing gives dp[3] + 1 = 12. Best 12 (rob it).
6	L6	return=12 houses=[1, 3, 5]	Maximum loot 12. Tracing the take/skip decisions backwards from house 5 gives the houses [1, 3, 5].

23.02.2

Define transition

Step two: express dp of a state using dp of smaller states. For minimum-cost stair climbing, with cost[i] paid when you stand on step i, you reach step i from step i - 1 or i - 2, so dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]), and the top (one past the last step) costs nothing extra, so the answer is the minimum of the last two.

Check each branch of the transition against the state sentence. If the transition mentions a quantity the state does not contain, the state is incomplete. The “Mixed costs” preset for costs 10, 15, 20, 5, 30, 8 shows each cell as the cost plus the better of two predecessors and ends with 28.

Java

1// dp[i] = least cost to arrive on step i having paid for step i itself
2static int minCostClimbingStairs(int[] cost) {
3    int n = cost.length;                         // at least two steps
4    int[] dp = new int[n];
5    dp[0] = cost[0];
6    dp[1] = cost[1];
7    for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
8    return Math.min(dp[n - 1], dp[n - 2]);       // the top is reached from either of the last two steps
9}

Min cost climbing stairs, with traceback

Interactive · edit the input

cost[i]

10i=0

15i=1

20i=2

5i=3

30i=4

8i=5

dp[i] = cheapest way to stand on i

10start

15start

?start

Setup

You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.

Step 1 / 7

Java

1static int minCost(int[] cost) {                 // you may start on step 0 or 1 and pay cost[i] when you leave step i
2    int n = cost.length; int[] dp = new int[n];  // dp[i] = cheapest total to stand on step i, including cost[i]
3    dp[0] = cost[0]; dp[1] = cost[1];
4    for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);   // best predecessor, then pay for this step
5    return Math.min(dp[n - 1], dp[n - 2]);        // the top is one step past the end, reached from either of the last two
6}

Live state

steps

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	steps=6	You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.
2	L4	i=2 dp[i-1]=15 dp[i-2]=10 dp[i]=30	dp[2] = cost[2] + min(15, 10) = 20 + 10 = 30. The cheaper predecessor is step 0 (remembered for the traceback).
3	L4	i=3 dp[i-1]=30 dp[i-2]=15 dp[i]=20	dp[3] = cost[3] + min(30, 15) = 5 + 15 = 20. The cheaper predecessor is step 1 (remembered for the traceback).
4	L4	i=4 dp[i-1]=20 dp[i-2]=30 dp[i]=50	dp[4] = cost[4] + min(20, 30) = 30 + 20 = 50. The cheaper predecessor is step 3 (remembered for the traceback).
5	L4	i=5 dp[i-1]=50 dp[i-2]=20 dp[i]=28	dp[5] = cost[5] + min(50, 20) = 8 + 20 = 28. The cheaper predecessor is step 3 (remembered for the traceback).
6	L5	top reached from=5 cost=28	The top (one step past the end) is cheapest from step 5: total 28.
7	L5	return=28 path=[1, 3, 5]	Minimum cost 28. Following the remembered predecessors backwards gives the steps stood on: [1, 3, 5].

23.02.3

Base cases

Step three: the **base cases** are the states whose answer is known without a recurrence, and they stop the recurrence from reading outside the table. Choose them by asking what the state sentence says about the smallest inputs. For stair climbing, ways[0] = 1 (one way to stay at the bottom: do nothing) and ways[1] = 1.

Mistakes here are common and quiet: dp[0] = 0 instead of 1 turns every count into zero. Read the state sentence for the empty case, and test with n = 0 and n = 1. The “n = 1” preset has 1 way and a table of two cells.

Java

1static long climbWays(int n) {
2    if (n <= 1) return 1;                        // base cases: ways[0] = 1 (do nothing), ways[1] = 1
3    long[] ways = new long[n + 1];
4    ways[0] = 1;
5    ways[1] = 1;
6    for (int i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2];
7    return ways[n];
8}

Climbing stairs: a table, then two variables

Interactive · edit the input

dp[i] = ways to reach step i

1i=0

1i=1

?i=2

?i=3

?i=4

?i=5

?i=6

?i=7

Setup

To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.

Step 1 / 8

Java

1static long ways(int n) {                         // dp[i] = number of ways to reach step i with moves of 1 or 2
2    long[] dp = new long[n + 1]; dp[0] = 1;       // one way to stand at the start: do nothing
3    if (n >= 1) dp[1] = 1;
4    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];   // arrive from i-1 or from i-2
5    return dp[n];
6}
7static long waysRolling(int n) {
8    long prev2 = 1, prev1 = 1;                    // dp[0], dp[1]
9    for (int i = 2; i <= n; i++) { long cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }   // forget what is no longer needed
10    return prev1;
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=7	To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.
2	L4	i=2 dp[i-1]=1 dp[i-2]=1 dp[i]=2	dp[2] = dp[1] + dp[0] = 1 + 1 = 2.
3	L4	i=3 dp[i-1]=2 dp[i-2]=1 dp[i]=3	dp[3] = dp[2] + dp[1] = 2 + 1 = 3.
4	L4	i=4 dp[i-1]=3 dp[i-2]=2 dp[i]=5	dp[4] = dp[3] + dp[2] = 3 + 2 = 5.
5	L4	i=5 dp[i-1]=5 dp[i-2]=3 dp[i]=8	dp[5] = dp[4] + dp[3] = 5 + 3 = 8.
6	L4	i=6 dp[i-1]=8 dp[i-2]=5 dp[i]=13	dp[6] = dp[5] + dp[4] = 8 + 5 = 13.
7	L4	i=7 dp[i-1]=13 dp[i-2]=8 dp[i]=21	dp[7] = dp[6] + dp[5] = 13 + 8 = 21.
8	L5	return=21	21 ways to climb 7 stairs. Time O(n); space O(n). This is the Fibonacci recurrence.

23.02.4

Evaluation order

Step four: decide the order in which states are computed so that every state is evaluated **after** the states it depends on. Bottom-up tabulation encodes the order in loops; top-down memoization lets the recursion find it. Because the dependency graph is a DAG, such an order always exists.

For one-dimensional recurrences on dp[i - 1] and dp[i - 2], increasing i works. For a grid recurrence on the cell above and the cell to the left, process rows top to bottom and, within a row, columns left to right. Reversing a loop that reads a not-yet-computed cell does not crash: it reads the zero the array was initialised with and silently gives a wrong answer.

Java

1// number of monotone paths in an m x n grid; each cell depends on the cell above and the cell to the left
2static long uniquePaths(int m, int n) {
3    long[][] ways = new long[m][n];
4    for (int i = 0; i < m; i++) {
5        for (int j = 0; j < n; j++) {
6            if (i == 0 || j == 0) ways[i][j] = 1;                       // first row and column
7            else ways[i][j] = ways[i - 1][j] + ways[i][j - 1];          // both already computed
8        }
9    }
10    return ways[m - 1][n - 1];
11}

Min cost climbing stairs, with traceback

Interactive · edit the input

cost[i]

10i=0

15i=1

20i=2

5i=3

30i=4

8i=5

dp[i] = cheapest way to stand on i

10start

15start

?start

Setup

You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.

Step 1 / 7

Java

1static int minCost(int[] cost) {                 // you may start on step 0 or 1 and pay cost[i] when you leave step i
2    int n = cost.length; int[] dp = new int[n];  // dp[i] = cheapest total to stand on step i, including cost[i]
3    dp[0] = cost[0]; dp[1] = cost[1];
4    for (int i = 2; i < n; i++) dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);   // best predecessor, then pay for this step
5    return Math.min(dp[n - 1], dp[n - 2]);        // the top is one step past the end, reached from either of the last two
6}

Live state

steps

No condition evaluated on this step

Execution trace (dry run table)Show 7 steps

Step	Line	State	What happens
1	L3	steps=6	You can start on step 0 or step 1, so dp[0] = cost[0] and dp[1] = cost[1]. Every later step is reached from one of the two steps below it.
2	L4	i=2 dp[i-1]=15 dp[i-2]=10 dp[i]=30	dp[2] = cost[2] + min(15, 10) = 20 + 10 = 30. The cheaper predecessor is step 0 (remembered for the traceback).
3	L4	i=3 dp[i-1]=30 dp[i-2]=15 dp[i]=20	dp[3] = cost[3] + min(30, 15) = 5 + 15 = 20. The cheaper predecessor is step 1 (remembered for the traceback).
4	L4	i=4 dp[i-1]=20 dp[i-2]=30 dp[i]=50	dp[4] = cost[4] + min(20, 30) = 30 + 20 = 50. The cheaper predecessor is step 3 (remembered for the traceback).
5	L4	i=5 dp[i-1]=50 dp[i-2]=20 dp[i]=28	dp[5] = cost[5] + min(50, 20) = 8 + 20 = 28. The cheaper predecessor is step 3 (remembered for the traceback).
6	L5	top reached from=5 cost=28	The top (one step past the end) is cheapest from step 5: total 28.
7	L5	return=28 path=[1, 3, 5]	Minimum cost 28. Following the remembered predecessors backwards gives the steps stood on: [1, 3, 5].

23.02.5

Answer extraction

Step five: know **where the answer lives**. It is often the last cell (dp[n]), but not always. Sometimes it is the best over all cells, because the solution may end anywhere: in the longest increasing subsequence the state 'longest subsequence ending exactly at index i' has the answer max(dp[i]). Sometimes it is dp at a target amount, or the minimum over a last row.

Decode ways ends at dp[n], the number of ways to decode the whole string; the “226” preset gives 3 (2-2-6, 22-6 and 2-26).

Java

1// dp[i] = length of the longest increasing subsequence that ENDS at index i
2static int lengthOfLis(int[] a) {
3    int n = a.length, best = 0;
4    int[] dp = new int[n];
5    for (int i = 0; i < n; i++) {
6        dp[i] = 1;
7        for (int j = 0; j < i; j++) if (a[j] < a[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
8        best = Math.max(best, dp[i]);            // the answer is the maximum over all end positions, not dp[n - 1]
9    }
10    return best;
11}

Decode ways: counting parses of a digit string

Interactive · edit the input

digits

dp[i] = decodings of the first i digits

1i=0

?i=1

?i=2

?i=3

Setup

dp[i] counts the ways to decode the first i digits. The last digit can be a letter by itself (1-9, never 0), or the last two digits can form a letter 10-26.

Step 1 / 5

Java

1static int numDecodings(String s) {                  // 'A'=1 ... 'Z'=26
2    int n = s.length(); int[] dp = new int[n + 1];     // dp[i] = ways to decode the first i digits
3    dp[0] = 1;                                         // the empty prefix has one decoding
4    for (int i = 1; i <= n; i++) {
5        if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];                            // last digit alone (1-9)
6        if (i >= 2 && s.charAt(i - 2) != '0' && Integer.parseInt(s.substring(i - 2, i)) <= 26) dp[i] += dp[i - 2];   // last two digits (10-26)
7    }
8    return dp[n];
9}

Live state

digits

No condition evaluated on this step

Execution trace (dry run table)Show 5 steps

Step	Line	State	What happens
1	L3	digits=3	dp[i] counts the ways to decode the first i digits. The last digit can be a letter by itself (1-9, never 0), or the last two digits can form a letter 10-26.
2	L5	i=1 dp[i]=1	dp[1] = 1: '2' alone adds dp[0] = 1.
3	L6	i=2 dp[i]=2	dp[2] = 2: '2' alone adds dp[1] = 1; "22" is a letter and adds dp[0] = 1.
4	L6	i=3 dp[i]=3	dp[3] = 3: '6' alone adds dp[2] = 2; "26" is a letter and adds dp[1] = 1.
5	L8	return=3	3 ways to decode "226". O(n) time; only the last two dp values are needed, so O(1) space is possible.

23.02.6

Complexity

Step six: the running time of a dynamic programming solution is **(number of states) × (work per state)**, which is the same as states plus transitions in the DAG view. The memory is the table size.

Coin change has amount + 1 states and up to k transitions each, so O(amount × k) time and O(amount) space. The 0/1 knapsack has (n + 1)(W + 1) states with two choices each: O(nW) time, which is *pseudo-polynomial* because W is a value, not a length. The input needs only log W bits, so the running time is exponential in the input size.

Problem	States	Work per state	Time	Space (full table)
Climbing stairs	n + 1	O(1)	O(n)	O(n)
House robber	n + 1	O(1)	O(n)	O(n)
Coin change	amount + 1	O(k) coins	O(amount · k)	O(amount)
0/1 knapsack	(n + 1)(W + 1)	O(1)	O(nW)	O(nW)
Longest increasing subsequence (this form)	n	O(n)	O(n²)	O(n)

Coin change: fewest coins, or number of ways

Interactive · edit the input

dp[a] = fewest coins

0a=0

∞a=1

∞a=2

∞a=3

∞a=4

∞a=5

∞a=6

last coin used

-a=0

-a=1

-a=2

-a=3

-a=4

-a=5

-a=6

Setup

dp[a] is the fewest coins that make a. dp[0] = 0, everything else starts at ∞ (not reachable yet). For each amount try every coin c: use one c and add 1 to the best for a − c.

Step 1 / 15

Java

1static int minCoins(int[] coins, int amount) {
2    int INF = amount + 1;
3    int[] dp = new int[amount + 1]; Arrays.fill(dp, INF); dp[0] = 0;             // dp[a] = fewest coins that make a
4    for (int a = 1; a <= amount; a++)
5        for (int c : coins)
6            if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;          // one coin c, then solve a - c
7    return dp[amount] >= INF ? -1 : dp[amount];
8}
9static long ways(int[] coins, int amount) {
10    long[] dp = new long[amount + 1]; dp[0] = 1;                                 // one way to make 0: take nothing
11    for (int c : coins)                                                          // coins in the outer loop: each combination is counted once
12        for (int a = c; a <= amount; a++) dp[a] += dp[a - c];
13    return dp[amount];
14}

Live state

amount

coins

[1, 3, 4]

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L3	amount=6 coins=[1, 3, 4]	dp[a] is the fewest coins that make a. dp[0] = 0, everything else starts at ∞ (not reachable yet). For each amount try every coin c: use one c and add 1 to the best for a − c.
2	L6	a=1 coin=1 candidate=1 dp[a]=1	Coin 1: dp[0] + 1 = 1 beats the old value: dp[1] = 1.
3	L6	a=2 coin=1 candidate=2 dp[a]=2	Coin 1: dp[1] + 1 = 2 beats the old value: dp[2] = 2.
4	L6	a=3 coin=1 candidate=3 dp[a]=3	Coin 1: dp[2] + 1 = 3 beats the old value: dp[3] = 3.
5	L6	a=3 coin=3 candidate=1 dp[a]=1	Coin 3: dp[0] + 1 = 1 beats the old value: dp[3] = 1.
6	L6	a=4 coin=1 candidate=2 dp[a]=2	Coin 1: dp[3] + 1 = 2 beats the old value: dp[4] = 2.
7	L6	a=4 coin=3 candidate=2 dp[a]=2	Coin 3: dp[1] + 1 = 2 does not improve dp[4] = 2.
8	L6	a=4 coin=4 candidate=1 dp[a]=1	Coin 4: dp[0] + 1 = 1 beats the old value: dp[4] = 1.
9	L6	a=5 coin=1 candidate=2 dp[a]=2	Coin 1: dp[4] + 1 = 2 beats the old value: dp[5] = 2.
10	L6	a=5 coin=3 candidate=3 dp[a]=2	Coin 3: dp[2] + 1 = 3 does not improve dp[5] = 2.
11	L6	a=5 coin=4 candidate=2 dp[a]=2	Coin 4: dp[1] + 1 = 2 does not improve dp[5] = 2.
12	L6	a=6 coin=1 candidate=3 dp[a]=3	Coin 1: dp[5] + 1 = 3 beats the old value: dp[6] = 3.
13	L6	a=6 coin=3 candidate=2 dp[a]=2	Coin 3: dp[3] + 1 = 2 beats the old value: dp[6] = 2.
14	L6	a=6 coin=4 candidate=3 dp[a]=2	Coin 4: dp[2] + 1 = 3 does not improve dp[6] = 2.
15	L7	return=2 coins=[3, 3]	Fewest coins: 2. Following the last coin used from 6 down to 0 gives the coins [3, 3]. Other optimal combinations may exist; the traceback shows the one the table remembers.

23.02.7

Space optimization

If a state depends only on a few previous states, keep only those. Stair climbing needs the last two values, so two variables replace the whole array: O(n) space becomes O(1) with the same loop. Compare the “n = 7, full table” and “n = 7, two variables” presets: both report 21, one with a table of 8 cells and one with two variables sliding along.

Do it last, after the table version is correct, because the table is what you debug. The same idea for two-dimensional tables keeps one or two rows; the optimisation lesson later in this chapter covers it.

Java

1static long climbWaysO1(int n) {
2    long prev = 1, cur = 1;                      // ways[i - 1] and ways[i], starting at i = 1
3    for (int i = 2; i <= n; i++) {
4        long next = prev + cur;
5        prev = cur;
6        cur = next;
7    }
8    return cur;
9}

Best

O(n)

Average

O(n)

Worst

O(n)

Space

O(1)

Climbing stairs: a table, then two variables

Interactive · edit the input

dp[i] = ways to reach step i

1i=0

1i=1

?i=2

?i=3

?i=4

?i=5

?i=6

?i=7

Setup

To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.

Step 1 / 8

Java

1static long ways(int n) {                         // dp[i] = number of ways to reach step i with moves of 1 or 2
2    long[] dp = new long[n + 1]; dp[0] = 1;       // one way to stand at the start: do nothing
3    if (n >= 1) dp[1] = 1;
4    for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];   // arrive from i-1 or from i-2
5    return dp[n];
6}
7static long waysRolling(int n) {
8    long prev2 = 1, prev1 = 1;                    // dp[0], dp[1]
9    for (int i = 2; i <= n; i++) { long cur = prev1 + prev2; prev2 = prev1; prev1 = cur; }   // forget what is no longer needed
10    return prev1;
11}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=7	To reach step i you arrive from step i−1 (one step) or step i−2 (two steps), so the ways add up: dp[i] = dp[i−1] + dp[i−2]. The base cases are dp[0] = 1 (start) and dp[1] = 1.
2	L4	i=2 dp[i-1]=1 dp[i-2]=1 dp[i]=2	dp[2] = dp[1] + dp[0] = 1 + 1 = 2.
3	L4	i=3 dp[i-1]=2 dp[i-2]=1 dp[i]=3	dp[3] = dp[2] + dp[1] = 2 + 1 = 3.
4	L4	i=4 dp[i-1]=3 dp[i-2]=2 dp[i]=5	dp[4] = dp[3] + dp[2] = 3 + 2 = 5.
5	L4	i=5 dp[i-1]=5 dp[i-2]=3 dp[i]=8	dp[5] = dp[4] + dp[3] = 5 + 3 = 8.
6	L4	i=6 dp[i-1]=8 dp[i-2]=5 dp[i]=13	dp[6] = dp[5] + dp[4] = 8 + 5 = 13.
7	L4	i=7 dp[i-1]=13 dp[i-2]=8 dp[i]=21	dp[7] = dp[6] + dp[5] = 13 + 8 = 21.
8	L5	return=21	21 ways to climb 7 stairs. Time O(n); space O(n). This is the Fibonacci recurrence.

Practice ladder

Now try it yourself

Easy

Min Cost Climbing Stairs
Counting Bits

Medium

Unique Paths
Longest Increasing Subsequence
Decode Ways

Advanced

Partition Equal Subset Sum
Maximum Product Subarray

Key takeaways

Define the state in a sentence, then the transition, then the base cases.
Evaluate states so dependencies come first; the DAG guarantees such an order exists.
Know where the answer lives: the last cell, a maximum over cells or a specific target.
Time is states times work per state; knapsack's O(nW) is pseudo-polynomial.
Reduce space last, after a correct table version exists.