🎛️ DP State Design — DP Guide | LeetCode Pattern Tracker

🎛️ The Most Important DP Skill

Beginners struggle with DP not because the math is hard, but because they don't know what to put in dp[]. This module teaches you to derive the state definition from first principles — every time.

The 3 Questions to Find Your State

What changes between recursive calls?

The parameters that change = your state dimensions.
House Robber: only i (current index) changes → 1D state dp[i]
LCS: both i and j (positions in two strings) change → 2D state dp[i][j]
Stocks with k transactions: day, k, holding → 3D state dp[day][k][holding]

What affects future decisions?

Only include in state what is necessary to make the optimal decision going forward.
Knapsack: need remaining_capacity because it limits future choices.
House Robber: do NOT need "how I got here" — only current index matters.
Stock cooldown: need holding flag because you can't buy if you already hold.

What does dp[state] represent?

Write it in English. This IS your recurrence.
dp[i] = max money robbing from house i to end
dp[i][w] = max value using first i items with capacity w
dp[i][j] = LCS length of s1[0..i] and s2[0..j]

State Dimension Reference

State	When to use	Examples	Space
`dp[i]`	Single sequence, one changing param	Fibonacci, House Robber, LIS	O(n)
`dp[i][j]`	Two sequences OR index + constraint	LCS, Edit Distance, Knapsack	O(n²)
`dp[i][j][k]`	Three constraints (often reducible)	Stocks with k txns, 3D Grid	O(n³)
`dp[row][col]`	2D grid movement	Unique Paths, Min Path Sum	O(m·n)
`dp[day][hold]`	State machine at each step	Stock Buy/Sell with cooldown	O(n)
`dp[mask]`	Subset of items visited (n≤20)	TSP, Bitmask DP	O(2ⁿ)
`dp[i][j]` interval	Subarray/substring of length j-i	MCM, Burst Balloons	O(n²)
`dp[node]`	Tree — depends on subtree results	House Robber III, Diameter	O(n)

Worked Examples — Deriving State from Scratch

Coin Change — LC 322

Problem: min coins to make amount

Q1: What changes? → remaining amount (after picking a coin)
Q2: What affects future? → only rem matters — once I choose a coin, the remaining amount fully determines future options
Q3: dp[rem] = min coins to make exactly rem

// State: dp[rem] = min coins to make amount rem
int[] dp = new int[amount+1];
Arrays.fill(dp, amount+1);  // "infinity"
dp[0] = 0;                  // base: 0 coins to make 0

for (int rem = 1; rem <= amount; rem++)
    for (int coin : coins)
        if (coin <= rem)
            dp[rem] = Math.min(dp[rem], dp[rem-coin] + 1);
// Recurrence: dp[rem] = min over all coins of (dp[rem-coin] + 1)
// "Use 1 coin + solve smaller subproblem"

State Reduction — From 3D to 1D

💡 Always try to reduce dimensions

If dp[i] only depends on dp[i-1] → use two variables. If dp[i][j] only depends on row i-1 → use 1D rolling array. This is what separates good solutions from great ones.

Original	Reduced	Trick
`dp[n]` Fibonacci	`a, b` — O(1)	Only need prev 2 values
`dp[n][W]` Knapsack	`dp[W]` — O(W)	Iterate weights in reverse
`dp[m][n]` LCS	`dp[n]` with prev var — O(n)	Row i only needs row i-1; save diagonal in `prev`
`dp[n][k][2]` Stocks	`buy, sell` arrays — O(k)	At each day only 2 states per transaction count