Dynamic Programming

When Is It DP?

The hardest part of DP is not writing the code — it is recognizing that the problem is DP in the first place. Use this framework:

The 5-Step Framework

Every DP solution follows these 5 steps. Memorize this — it turns an intimidating open-ended problem into a structured fill-in-the-blanks exercise.

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart TD
    S1["Step 1: Define State\n'What params describe a subproblem?'"]
    S2["Step 2: Write Recurrence\n'How does dp[current] relate to smaller states?'"]
    S3["Step 3: Base Cases\n'What is trivially solvable?'"]
    S4["Step 4: Iteration Order\n'Ensure dependencies computed first'"]
    S5["Step 5: Space Optimization\n'Can I drop old rows/states?'"]

    S1 --> S2 --> S3 --> S4 --> S5

    style S1 fill:#DCFCE7,stroke:#16A34A,stroke-width:2px,color:#14532D
    style S2 fill:#DBEAFE,stroke:#2563EB,stroke-width:2px,color:#1E3A5F
    style S3 fill:#FEF3C7,stroke:#D97706,stroke-width:2px,color:#78350F
    style S4 fill:#FEE2E2,stroke:#DC2626,stroke-width:2px,color:#7F1D1D
    style S5 fill:#E0E7FF,stroke:#4F46E5,stroke-width:2px,color:#312E81

DP Categories

1. 1D Linear DP

State: dp[i] = answer considering the first i elements.

When to use: Problems where you process elements left to right and the decision at position i depends only on a fixed number of previous positions.

public int solve(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = /* base case */;

    for (int i = 1; i < n; i++) {
        dp[i] = /* recurrence using dp[i-1], dp[i-2], etc. */;
    }
    return dp[n - 1];
}

public int solve(int[] nums) {
    int prev2 = /* base for dp[0] */;
    int prev1 = /* base for dp[1] */;

    for (int i = 2; i < nums.length; i++) {
        int curr = /* recurrence using prev1, prev2 */;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Key Problems: Climbing Stairs, House Robber, Maximum Subarray, Decode Ways, Jump Game II

2. 2D Grid DP

State: dp[i][j] = answer at position (i, j) in a grid.

When to use: Problems on a 2D grid where you can only move right/down (or limited directions), and you need min cost, number of paths, etc.

public int solve(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0]; // or 1 for path counting

    // Fill first row
    for (int j = 1; j < n; j++)
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    // Fill first column
    for (int i = 1; i < m; i++)
        dp[i][0] = dp[i - 1][0] + grid[i][0];

    // Fill rest
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];

    return dp[m - 1][n - 1];
}

public int solve(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = grid[0][0];

    for (int j = 1; j < n; j++)
        dp[j] = dp[j - 1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++)
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
    }
    return dp[n - 1];
}

Key Problems: Unique Paths, Minimum Path Sum, Dungeon Game, Maximal Square

3. Knapsack DP

State: dp[i][w] = best value using first i items with capacity w.

When to use: You have items with weight/cost and value, and a capacity constraint. Also applies to subset sum, partition problems, and coin change variants.

public int knapsack01(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // skip item i
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]); // take item i
            }
        }
    }
    return dp[n][capacity];
}

public int knapsackUnbounded(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int w = 0; w <= capacity; w++) {
        for (int i = 0; i < weights.length; i++) {
            if (weights[i] <= w) {
                dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
            }
        }
    }
    return dp[capacity];
}

// Key insight: iterate capacity BACKWARDS to avoid using same item twice
public int knapsack01Optimized(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < weights.length; i++) {
        for (int w = capacity; w >= weights[i]; w--) { // backwards!
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Key Problems: Subset Sum, Partition Equal Subset Sum, Coin Change, Target Sum

4. String DP

State: dp[i][j] = answer for s1[0..i-1] and s2[0..j-1].

When to use: Problems comparing two strings/sequences — edit distance, longest common subsequence, regex matching.

public int solve(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    // Base cases: dp[i][0] and dp[0][j]
    for (int i = 0; i <= m; i++) dp[i][0] = /* base */;
    for (int j = 0; j <= n; j++) dp[0][j] = /* base */;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + /* match logic */;
            } else {
                dp[i][j] = /* mismatch: combine dp[i-1][j], dp[i][j-1], dp[i-1][j-1] */;
            }
        }
    }
    return dp[m][n];
}

Key Problems: Longest Common Subsequence, Edit Distance, Longest Palindromic Subsequence, Regular Expression Matching, Wildcard Matching

5. Interval DP

State: dp[i][j] = answer for the subarray/substring from index i to j.

When to use: Problems where you try all possible "split points" in a range — matrix chain multiplication, burst balloons, palindrome partitioning.

public int solve(int[] nums) {
    int n = nums.length;
    int[][] dp = new int[n][n];

    // Base: single elements (length 1)
    for (int i = 0; i < n; i++) dp[i][i] = /* base */;

    // Fill by increasing length
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE; // or MIN_VALUE for max problems
            for (int k = i; k < j; k++) { // try all split points
                dp[i][j] = Math.min(dp[i][j],
                    dp[i][k] + dp[k + 1][j] + /* cost of combining */);
            }
        }
    }
    return dp[0][n - 1];
}

Key Problems: Burst Balloons, Matrix Chain Multiplication, Palindrome Partitioning II, Stone Game

6. State Machine DP

State: Includes which "state" or "phase" you are in. Useful when there are rules about what transitions are allowed.

public int maxProfit(int[] prices) {
    int n = prices.length;
    // States: held (holding stock), sold (just sold), rest (cooldown/idle)
    int[] held = new int[n];
    int[] sold = new int[n];
    int[] rest = new int[n];

    held[0] = -prices[0];
    sold[0] = 0;
    rest[0] = 0;

    for (int i = 1; i < n; i++) {
        held[i] = Math.max(held[i-1], rest[i-1] - prices[i]); // keep or buy
        sold[i] = held[i-1] + prices[i];                       // sell
        rest[i] = Math.max(rest[i-1], sold[i-1]);              // stay idle
    }
    return Math.max(sold[n-1], rest[n-1]);
}

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
stateDiagram-v2
    [*] --> Rest
    Rest --> Rest: wait
    Rest --> Held: buy
    Held --> Held: wait
    Held --> Sold: sell
    Sold --> Rest: cooldown (forced)

Key Problems: Best Time to Buy/Sell Stock II/III/IV/with Cooldown/with Transaction Fee

7. Bitmask DP

State: dp[mask] or dp[mask][i] where mask is a bitmask representing which elements have been used/visited.

When to use: Problems involving permutations or subsets where n is small (n <= 20). The bitmask encodes "which items are chosen" in O(2^n) states.

public int solve(int[][] dist, int n) {
    int[][] dp = new int[1 << n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
    dp[1][0] = 0; // start at node 0

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (dp[mask][u] == Integer.MAX_VALUE) continue;
            if ((mask & (1 << u)) == 0) continue; // u not in mask
            for (int v = 0; v < n; v++) {
                if ((mask & (1 << v)) != 0) continue; // v already visited
                int newMask = mask | (1 << v);
                dp[newMask][v] = Math.min(dp[newMask][v],
                    dp[mask][u] + dist[u][v]);
            }
        }
    }
    // Find min cost to visit all nodes
    int full = (1 << n) - 1;
    int ans = Integer.MAX_VALUE;
    for (int u = 0; u < n; u++)
        ans = Math.min(ans, dp[full][u]);
    return ans;
}

Key Problems: Travelling Salesman, Shortest Superstring, Can I Win, Partition to K Equal Sum Subsets (n <= 16)

Solved Walkthroughs

Problem 1: House Robber (LC #198) — 1D DP

Step 1: Why Greedy Fails

You might think "just pick the largest elements that are not adjacent." But that does not work — you need to consider the global picture. The decision at each house (rob or skip) affects future options.

Step 2: Recursive Decision Tree (shows overlapping subproblems)

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
graph TD
    R0["rob(0)\n= max(2+rob(2), rob(1))"]
    R1["rob(1)\n= max(7+rob(3), rob(2))"]
    R2["rob(2)\n= max(9+rob(4), rob(3))"]
    R3["rob(3)\n= max(3, 0)"]
    R4["rob(4)\n= max(1, 0)"]

    R0 --> R2
    R0 --> R1
    R1 --> R3
    R1 --> R2
    R2 --> R4
    R2 --> R3

    style R2 fill:#FEE2E2,stroke:#DC2626,stroke-width:2px,color:#7F1D1D
    style R3 fill:#FEE2E2,stroke:#DC2626,stroke-width:2px,color:#7F1D1D

Notice rob(2) and rob(3) are computed multiple times — overlapping subproblems confirmed.

Step 3: Memoization (Top-Down)

public int rob(int[] nums) {
    int[] memo = new int[nums.length];
    Arrays.fill(memo, -1);
    return robFrom(nums, 0, memo);
}

private int robFrom(int[] nums, int i, int[] memo) {
    if (i >= nums.length) return 0;
    if (memo[i] != -1) return memo[i];

    // Choice: rob this house + skip next, OR skip this house
    memo[i] = Math.max(
        nums[i] + robFrom(nums, i + 2, memo),
        robFrom(nums, i + 1, memo)
    );
    return memo[i];
}

Step 4: Tabulation (Bottom-Up)

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    return dp[nums.length - 1];
}

Step 5: Space Optimization — O(1)

public int rob(int[] nums) {
    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];

    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);

    for (int i = 2; i < nums.length; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Complexity: Time O(n), Space O(1)

Problem 2: Coin Change (LC #322) — Unbounded Knapsack

Why Greedy Fails

With coins [1, 3, 4] and amount 6:

• Greedy (largest first): 4 + 1 + 1 = 3 coins
• DP (optimal): 3 + 3 = 2 coins

Greedy fails because taking the largest coin does not always lead to the global minimum.

Build the DP Table Step by Step

State: dp[a] = minimum coins to make amount a

Recurrence: dp[a] = min(dp[a - coin] + 1) for each coin where coin <= a

Base case: dp[0] = 0 (zero coins needed for amount 0)

Memoization (Top-Down)

public int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, -2); // -2 = not computed
    int result = dp(coins, amount, memo);
    return result;
}

private int dp(int[] coins, int amount, int[] memo) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    if (memo[amount] != -2) return memo[amount];

    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        int sub = dp(coins, amount - coin, memo);
        if (sub != -1) {
            min = Math.min(min, sub + 1);
        }
    }
    memo[amount] = (min == Integer.MAX_VALUE) ? -1 : min;
    return memo[amount];
}

Tabulation (Bottom-Up)

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // "infinity"
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a) {
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Complexity: Time O(amount * coins.length), Space O(amount)

Problem 3: Longest Common Subsequence (LC #1143) — String DP

The 2D Table — Visual Fill

State: dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1]

Recurrence:

• If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (characters match, extend LCS)
• Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (skip one character from either string)

Bold entries show where characters matched and the diagonal was extended.

Tabulation

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Space Optimization — O(n) with Two Rows

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                curr[j] = prev[j - 1] + 1;
            } else {
                curr[j] = Math.max(prev[j], curr[j - 1]);
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
        Arrays.fill(curr, 0);
    }
    return prev[n];
}

Complexity: Time O(m*n), Space O(min(m,n))

Problem 4: Edit Distance (LC #72) — String DP

How Operations Map to DP Transitions

State: dp[i][j] = min edits to convert word1[0..i-1] into word2[0..j-1]

Recurrence:

• If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation needed)
• Else: dp[i][j] = 1 + min(
  • dp[i-1][j-1] → replace word1[i-1] with word2[j-1]
  • dp[i-1][j] → delete word1[i-1]
  • dp[i][j-1] → insert word2[j-1] after word1[i-1]
  • )

%%{init: {'theme': 'base', 'themeVariables': {'fontSize': '13px', 'fontFamily': 'Inter, -apple-system, sans-serif'}, 'flowchart': {'nodeSpacing': 30, 'rankSpacing': 50, 'padding': 12, 'curve': 'basis'}, 'sequence': {'actorMargin': 60, 'messageMargin': 40}, 'class': {'padding': 12}}}%%
flowchart LR
    subgraph "dp[i-1][j-1]"
        A["Replace"]
    end
    subgraph "dp[i-1][j]"
        B["Delete"]
    end
    subgraph "dp[i][j-1]"
        C["Insert"]
    end
    A --> D["dp[i][j]\n= 1 + min(all three)"]
    B --> D
    C --> D

Base Cases

• dp[i][0] = i (delete all i characters from word1)
• dp[0][j] = j (insert all j characters of word2)

Fill the Table: "horse" to "ros"

Tabulation

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j - 1], // replace
                    Math.min(dp[i - 1][j], dp[i][j - 1]) // delete, insert
                );
            }
        }
    }
    return dp[m][n];
}

Space Optimization — O(n)

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[] prev = new int[n + 1];
    int[] curr = new int[n + 1];

    for (int j = 0; j <= n; j++) prev[j] = j;

    for (int i = 1; i <= m; i++) {
        curr[0] = i;
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                curr[j] = prev[j - 1];
            } else {
                curr[j] = 1 + Math.min(prev[j - 1],
                    Math.min(prev[j], curr[j - 1]));
            }
        }
        int[] temp = prev;
        prev = curr;
        curr = temp;
    }
    return prev[n];
}

Complexity: Time O(m*n), Space O(n)

Top-Down vs Bottom-Up

Space Optimization Techniques

Rolling Array (Two Rows)

When dp[i] only depends on dp[i-1], keep only two rows and alternate:

int[] prev = new int[n + 1];
int[] curr = new int[n + 1];
// After computing curr row:
int[] temp = prev;
prev = curr;
curr = temp;

Single Row (In-Place)

When dp[i][j] depends only on dp[i-1][j] (directly above) and dp[i][j-1] (left), you can use a single row — the "above" value is the old value at dp[j] before overwriting:

int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        dp[j] = /* dp[j] is "above", dp[j-1] is "left" */;
    }
}

int prev_diag = dp[0];
for (int j = 1; j <= n; j++) {
    int temp = dp[j]; // save current (will become prev_diag next iteration)
    dp[j] = /* use prev_diag for dp[i-1][j-1] */;
    prev_diag = temp;
}

Two Variables (O(1) Space)

When dp[i] only depends on dp[i-1] and dp[i-2] (e.g., Fibonacci, Climbing Stairs, House Robber):

int prev2 = base0, prev1 = base1;
for (int i = 2; i < n; i++) {
    int curr = f(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
}

Common Mistakes

if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0]; // often a special case

Practice Problems

1D Linear DP

2D Grid DP

Knapsack Variants

String DP

Interval & State Machine

How to Approach a New DP Problem in an Interview

When you are stuck, follow this checklist in order:

Interview Communication Script

"I notice this problem has optimal substructure and overlapping subproblems —
I think DP is the right approach."

"Let me define the state: dp[i] represents..."

"The recurrence is: at each position, I can either... or...,
so dp[i] = max/min of those choices."

"Base cases: when i = 0, the answer is trivially..."

"Let me trace through the example to verify..."
[Trace 2-3 cells of the DP table on the whiteboard]

"Time complexity is O(...), space is O(...).
I can optimize space to O(...) using a rolling array — shall I implement that?"

Quick Reference Card

┌─────────────────────────────────────────────────────────────┐
│  DP PATTERN SELECTION GUIDE                                  │
├─────────────────────────────────────────────────────────────┤
│  "Min/max considering first i elements"  →  1D Linear DP    │
│  "Path/count in a grid"                  →  2D Grid DP      │
│  "Select items with capacity limit"      →  Knapsack DP     │
│  "Compare/transform two strings"         →  String DP       │
│  "Best answer for subarray [i..j]"       →  Interval DP     │
│  "Allowed transitions between phases"    →  State Machine   │
│  "Subset of n <= 20 items"               →  Bitmask DP      │
├─────────────────────────────────────────────────────────────┤
│  SPACE OPTIMIZATION RULE OF THUMB                            │
│  dp[i] depends on dp[i-1] only        →  two rows / O(n)   │
│  dp[i] depends on dp[i-1] & dp[i-2]   →  two variables     │
│  dp[i][j] needs diagonal               →  save prev_diag    │
│  interval DP (dp[i][j] for all pairs)  →  usually no opt    │
└─────────────────────────────────────────────────────────────┘

Was this helpful?

Yes Needs more

Thanks for your feedback!

Discussion

Markdown supported Post

Sign in to join the discussion Sign In

Loading comments...