Study Notes by Niladri & AI

Session-10-DP2D

Properties1
tagsdynamic-programming, dp-2d, interval-dp, interview-prep, java

23 min read

Practice Session 10: Dynamic Programming — 2D / Multi-Sequence Problems

Overview

2D DP generalizes the 1D DP idea: instead of a single index tracking “how much we’ve consumed”, we need a pair of indices (i, j) to fully describe the state. The two dimensions are almost always independent — advancing i doesn’t force advancing j — which is what makes memoizing their cross-product valid. At senior level, the key skill is recognizing which two dimensions define the state and writing the recurrence cleanly. Space optimization via rolling arrays reduces O(m·n) space to O(min(m,n)) and is expected in any senior interview on this topic. Interval DP (Burst Balloons) is the hardest sub-class: the dimension is a range [i..j] rather than a prefix, and the “last operation” framing is the classic trick to make sub-problems independent.

Problem 1: Unique Paths

Link: LeetCode 62

Quick Summary: Count the number of distinct paths from the top-left to the bottom-right corner of an m×n grid, moving only right or down.

Industry Context: Route enumeration in constrained grids appears in robotics path planning (counting feasible trajectories under movement constraints), UI layout engines (how many ways a flex container can distribute remaining space across cells), and integration testing (counting distinct execution paths through a DAG of service calls with at most one direction per step). The combinatorics reduction (C(m+n-2, m-1)) also appears in probability calculations for random walks.

Approach 1: Naive Recursion

// Time: O(2^(m+n))  Space: O(m+n) stack
public static int uniquePathsRecursive(int m, int n) {
    return uniquePathsHelper(m, n, 0, 0);
}
 
private static int uniquePathsHelper(int m, int n, int row, int col) {
    if (row == m - 1 && col == n - 1) return 1;
    if (row >= m || col >= n) return 0;
    return uniquePathsHelper(m, n, row + 1, col)
         + uniquePathsHelper(m, n, row, col + 1);
}
  • Time: O(2^(m+n)) — exponential; every call branches into two sub-calls
  • Space: O(m+n) — recursion depth equals path length (m-1 + n-1)
  • Tradeoff: Correct but exponential. A 10×10 grid already has millions of recursive calls. This is the signal: two choices at each step + overlapping sub-problems = DP candidate.

Approach 2: 2D DP Table

// Time: O(m*n)  Space: O(m*n)
public static int uniquePaths2DDP(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) dp[i][0] = 1;
    for (int j = 0; j < n; j++) dp[0][j] = 1;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    return dp[m - 1][n - 1];
}
  • Time: O(m·n)
  • Space: O(m·n)
  • Key Insight: The table is literally Pascal’s Triangle laid in 2D. dp[i][j] = the binomial coefficient C(i+j, i). The border cells are all 1 (only one way to reach them — move entirely in one direction). Each interior cell sums its two predecessors.

DP Table for 3×3 grid:

     col0  col1  col2
row0 [  1    1    1  ]
row1 [  1    2    3  ]
row2 [  1    3    6  ]

Answer: dp[2][2] = 6. Each cell = cell above + cell to the left.

Approach 3: Space-Optimized 1D Rolling Array

// Time: O(m*n)  Space: O(n)
public static int uniquePathsSpaceOptimized(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);           // first row: all 1s
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j - 1];  // dp[j] = above (old dp[j]) + left (dp[j-1])
        }
    }
    return dp[n - 1];
}
  • Time: O(m·n)
  • Space: O(n) — one row only

Approach 4: Combinatorics O(min(m,n)) Time, O(1) Space

// Time: O(min(m,n))  Space: O(1)
public static int uniquePathsCombinatorics(int m, int n) {
    int total = m + n - 2;
    int choose = Math.min(m - 1, n - 1);
    long result = 1;
    for (int i = 0; i < choose; i++) {
        result = result * (total - i) / (i + 1);
    }
    return (int) result;
}
  • Time: O(min(m,n))
  • Space: O(1)
  • Key Insight: Any valid path takes exactly (m-1) down-moves and (n-1) right-moves. The answer is the number of ways to arrange them: C(m+n-2, m-1). This is the mathematically cleanest solution but requires the insight that all paths have the same length.

Recurrence relation:

dp[i][j] = dp[i-1][j] + dp[i][j-1]
dp[i][0] = dp[0][j] = 1  (base case: border cells)

Problem 2: Longest Common Subsequence

Link: LeetCode 1143

Quick Summary: Given two strings, return the length of their longest common subsequence (characters need not be contiguous but must be in order).

Industry Context: LCS is the mathematical foundation of diff tools — git diff and UNIX diff compute LCS of lines between file versions (Myers’ algorithm is a graph shortest-path formulation over the same DP state space). In bioinformatics, Needleman-Wunsch global sequence alignment and Smith-Waterman local alignment are scored LCS variants used in BLAST and genome assembly pipelines to find conserved gene regions across species. LCS also powers plagiarism detection systems that compare document token sequences.

Approach 1: Naive Recursion

// Time: O(2^(m+n))  Space: O(m+n) stack
public static int lcsRecursive(String text1, String text2) {
    return lcsHelper(text1, text2, 0, 0);
}
 
private static int lcsHelper(String s1, String s2, int i, int j) {
    if (i == s1.length() || j == s2.length()) return 0;
    if (s1.charAt(i) == s2.charAt(j)) {
        return 1 + lcsHelper(s1, s2, i + 1, j + 1);
    }
    return Math.max(
        lcsHelper(s1, s2, i + 1, j),
        lcsHelper(s1, s2, i, j + 1)
    );
}
  • Time: O(2
  • Space: O(m+n)
  • Tradeoff: Recomputes the same (i,j) pairs exponentially. For “abcde” vs “ace”, the pair (2,1) is reached by many different recursion paths.

Approach 2: 2D DP Table (Optimal)

// Time: O(m*n)  Space: O(m*n)
public static int lcs2DDP(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] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}
  • Time: O(m·n)
  • Space: O(m·n)
  • Key Insight: dp[i][j] represents the LCS of text1[0..i-1] and text2[0..j-1]. Using 1-indexed arrays with a row/column of zeros as base cases is the cleanest formulation — it eliminates all boundary condition special-casing.

Recurrence relation:

dp[i][j] = 1 + dp[i-1][j-1]            if text1[i-1] == text2[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise
dp[i][0] = dp[0][j] = 0                 (base case: empty prefix)

Full DP Table Visualization — “abcde” vs “ace”:

        ""   a    c    e
    ""  [ 0   0    0    0 ]
    a   [ 0   1    1    1 ]
    b   [ 0   1    1    1 ]
    c   [ 0   1    2    2 ]
    d   [ 0   1    2    2 ]
    e   [ 0   1    2    3 ]  ← answer: dp[5][3] = 3

Reading the table:

  • dp[1][1]: ‘a’==‘a’ → 1 + dp[0][0] = 1
  • dp[3][2]: ‘c’==‘c’ → 1 + dp[2][1] = 2
  • dp[5][3]: ‘e’==‘e’ → 1 + dp[4][2] = 3

Geometric intuition: a diagonal move (↖) happens when characters match and extends the LCS by 1. An up or left move (↑ or ←) happens when we skip a character. The LCS is the number of diagonal moves on the optimal path from (m,n) back to (0,0).

Approach 3: Space-Optimized Two-Row

// Time: O(m*n)  Space: O(n)
public static int lcsSpaceOptimized(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] = 1 + prev[j - 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];
}
  • Time: O(m·n)
  • Space: O(n) — two rows, swapped each iteration

Problem 3: Edit Distance

Link: LeetCode 72

Quick Summary: Given two words, return the minimum number of single-character operations (insert, delete, replace) needed to transform word1 into word2.

Industry Context: Edit distance (Levenshtein distance) is the backbone of spell checkers and autocorrect — iOS and Android keyboard autocorrect rank candidate words by their edit distance from the typed token, with beam search over the top-k nearest words. git diff at the character level uses a weighted edit distance variant. Search engines use edit distance for fuzzy query matching (“did you mean…?”). In database deduplication (entity resolution), record pairs with edit distance below a threshold are merged as duplicates. The space-optimized version is critical in production since vocabulary sizes are 500k+ words.

Approach 1: Naive Recursion

// Time: O(3^(m+n))  Space: O(m+n) stack
public static int editDistanceRecursive(String word1, String word2) {
    return editDistanceHelper(word1, word2, 0, 0);
}
 
private static int editDistanceHelper(String w1, String w2, int i, int j) {
    if (i == w1.length()) return w2.length() - j;  // insert remaining
    if (j == w2.length()) return w1.length() - i;  // delete remaining
    if (w1.charAt(i) == w2.charAt(j)) {
        return editDistanceHelper(w1, w2, i + 1, j + 1);
    }
    int insert  = 1 + editDistanceHelper(w1, w2, i,     j + 1);
    int delete  = 1 + editDistanceHelper(w1, w2, i + 1, j);
    int replace = 1 + editDistanceHelper(w1, w2, i + 1, j + 1);
    return Math.min(insert, Math.min(delete, replace));
}
  • Time: O(3^(m+n)) — three branches on mismatch
  • Space: O(m+n) stack

Approach 2: 2D DP Table (Levenshtein Matrix)

// Time: O(m*n)  Space: O(m*n)
public static int editDistance2DDP(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;  // delete all i chars
    for (int j = 0; j <= n; j++) dp[0][j] = j;  // insert all j chars
 
    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];             // free match
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],  // replace
                               Math.min(dp[i - 1][j],       // delete
                                        dp[i][j - 1]));     // insert
            }
        }
    }
    return dp[m][n];
}
  • Time: O(m·n)
  • Space: O(m·n)

Recurrence relation:

dp[i][j] = dp[i-1][j-1]                                  if word1[i-1] == word2[j-1]
dp[i][j] = 1 + min(dp[i-1][j-1],  dp[i-1][j],  dp[i][j-1])  otherwise
             (replace)              (delete)     (insert)

Base cases:  dp[i][0] = i  (delete i chars to reach empty)
             dp[0][j] = j  (insert j chars from empty)

Full DP Table Visualization — “horse” → “ros” (answer: 3):

        ""   r    o    s
    ""  [ 0   1    2    3 ]
    h   [ 1   1    2    3 ]
    o   [ 2   2    1    2 ]
    r   [ 3   2    2    2 ]
    s   [ 4   3    3    2 ]
    e   [ 5   4    4    3 ]  ← answer: dp[5][3] = 3

Reading the table step by step:

  • dp[1][1]: ‘h’ vs ‘r’ → mismatch → 1 + min(dp[0][0]=0, dp[0][1]=1, dp[1][0]=1) = 1
  • dp[2][2]: ‘o’ vs ‘o’ → match → dp[1][1] = 1
  • dp[5][3]: ‘e’ vs ‘s’ → mismatch → 1 + min(dp[4][2]=3, dp[4][3]=2, dp[5][2]=4) = 3

Geometric intuition for operations:

Moving ↖ diagonally (i-1,j-1) → (i,j):
  - Characters match: FREE (cost 0) — just advance both pointers
  - Characters differ: REPLACE (cost 1) — pay 1 to align them

Moving ↑ up (i-1,j) → (i,j):
  - DELETE word1[i-1]: we consumed a char from word1 without matching

Moving ← left (i,j-1) → (i,j):
  - INSERT word2[j-1]: we consumed a char from word2, inserting it into word1

The DP table finds the cheapest sequence of moves (cheapest path)
from top-left corner (0,0) to bottom-right (m,n).

Approach 3: Space-Optimized (Two-Row)

// Time: O(m*n)  Space: O(n)
public static int editDistanceSpaceOptimized(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;  // base case: empty word1
 
    for (int i = 1; i <= m; i++) {
        curr[0] = i;  // base case: empty word2 at this row
        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],       // replace
                               Math.min(prev[j],           // delete
                                        curr[j - 1]));     // insert
            }
        }
        int[] temp = prev; prev = curr; curr = temp;
    }
    return prev[n];
}
  • Time: O(m·n)
  • Space: O(n) — two rows only

Problem 4: Coin Change II

Link: LeetCode 518

Quick Summary: Given coin denominations and a target amount, count the number of distinct combinations (not permutations) of coins that sum to the target. Each coin can be used unlimited times.

Industry Context: Coin Change II is a textbook unbounded knapsack problem. In financial engineering, this models portfolio rebalancing with discrete instruments: given a set of bond/ETF denominations and a target notional value, count the distinct ways to construct that notional using unlimited units of each instrument. In compiler register allocation, the problem maps to counting distinct instruction sequences of given sizes that fill a basic block of target size. The key insight — outer loop over coins, inner over amounts — ensures we count combinations (not permutations), which is essential in any “how many distinct ways” problem.

Approach 1: 2D DP (Combinations Count — Unbounded Knapsack)

// Time: O(amount * coins.length)  Space: O(amount * coins.length)
public static int coinChange2_2DDP(int[] coins, int amount) {
    int n = coins.length;
    int[][] dp = new int[n + 1][amount + 1];
    for (int i = 0; i <= n; i++) dp[i][0] = 1;  // 1 way to make 0: use nothing
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= amount; j++) {
            dp[i][j] = dp[i - 1][j];             // don't use coin i
            if (j >= coins[i - 1]) {
                dp[i][j] += dp[i][j - coins[i - 1]];  // use coin i (unbounded)
            }
        }
    }
    return dp[n][amount];
}
  • Time: O(amount · |coins|)
  • Space: O(amount · |coins|)
  • Key Insight — combinations vs. permutations: Iterating coins in the outer loop means each coin is processed in a separate “wave”. Once we move past coin i, it can no longer be the “first new coin” we consider, preventing the same combination from being counted in different orders. If we iterated amounts in the outer loop, we’d get permutations (LC 377 = permutation variant).

DP Table Visualization — coins=[1,2,5], amount=5:

         amt=0  1  2  3  4  5
no coins [  1   0  0  0  0  0 ]
coin=1   [  1   1  1  1  1  1 ]
coin=2   [  1   1  2  2  3  3 ]
coin=5   [  1   1  2  2  3  4 ]  ← answer: dp[3][5] = 4

The 4 combinations are: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}, {5}.

Approach 2: Space-Optimized 1D DP

// Time: O(amount * coins.length)  Space: O(amount)
public static int coinChange2_1DDP(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // 1 way to make 0
 
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    return dp[amount];
}
  • Time: O(amount · |coins|)
  • Space: O(amount)
  • Key Insight — left-to-right traversal for unbounded: Updating dp[j] from left to right means when we compute dp[j] += dp[j-coin], dp[j-coin] has already been updated in this coin’s iteration — meaning we’ve potentially used this coin multiple times. That is exactly what unbounded allows. Compare to 0/1 knapsack which traverses right-to-left to prevent reuse.

Recurrence relation:

dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]]   (if j >= coins[i-1])
dp[i][j] = dp[i-1][j]                              (otherwise)
dp[i][0] = 1  (base: 1 way to make 0)

Problem 5: Burst Balloons

Link: LeetCode 312

Quick Summary: Given n balloons with values, burst all balloons to maximize coins collected. Bursting balloon i (with neighbors j and k) gives nums[j] * nums[i] * nums[k] coins, and the balloons close the gap.

Industry Context: The interval DP structure in Burst Balloons appears in query plan optimization (finding the optimal order to apply join operations in a query tree — structurally identical to Matrix Chain Multiplication), game-tree alpha-beta pruning over intervals of moves, and optimal expression evaluation ordering in compilers. The “last operation” insight — thinking about which operation to perform LAST rather than first — is a general technique in interval DP that removes the sub-problem dependency that makes “first operation” reasoning intractable.

The Core Insight: “Last Balloon” Framing

Why “first balloon” fails: If we pick balloon k first in interval [left, right], then its neighbors become the remaining balloons on either side — but those neighbors depend on which other balloons have been burst. This creates a dependency between the left and right sub-problems.

Why “last balloon” works: If balloon k is the LAST burst in interval (left, right), then when we burst it:

  • All balloons in (left, k) are already gone — left boundary is nums[left]
  • All balloons in (k, right) are already gone — right boundary is nums[right]
  • Coins = nums[left] * nums[k] * nums[right] (a fixed, deterministic value)
  • Sub-problems (left, k) and (k, right) are completely independent of each other

This independence is why the recurrence is valid. The padding with 1s on both ends creates virtual boundary balloons that are never burst themselves.

Approach 1: Memoized Top-Down Interval DP

// Time: O(n^3)  Space: O(n^2)
public static int maxCoinsTopDown(int[] nums) {
    int n = nums.length;
    int[] padded = new int[n + 2];
    padded[0] = padded[n + 1] = 1;
    for (int i = 0; i < n; i++) padded[i + 1] = nums[i];
 
    int[][] memo = new int[n + 2][n + 2];
    for (int[] row : memo) Arrays.fill(row, -1);
    return burstHelper(padded, memo, 0, n + 1);
}
 
// Returns max coins for bursting all balloons strictly between left and right
private static int burstHelper(int[] nums, int[][] memo, int left, int right) {
    if (right - left < 2) return 0;
    if (memo[left][right] != -1) return memo[left][right];
 
    int maxCoins = 0;
    for (int k = left + 1; k < right; k++) {
        int coins = nums[left] * nums[k] * nums[right]
                  + burstHelper(nums, memo, left, k)
                  + burstHelper(nums, memo, k, right);
        maxCoins = Math.max(maxCoins, coins);
    }
    memo[left][right] = maxCoins;
    return maxCoins;
}
  • Time: O(n^3) — O(n^2) states × O(n) work per state
  • Space: O(n^2) — memoization table

Approach 2: Bottom-Up Interval DP

// Time: O(n^3)  Space: O(n^2)
public static int maxCoinsBottomUp(int[] nums) {
    int n = nums.length;
    int[] p = new int[n + 2];
    p[0] = p[n + 1] = 1;
    for (int i = 0; i < n; i++) p[i + 1] = nums[i];
 
    int size = n + 2;
    int[][] dp = new int[size][size];
 
    for (int len = 2; len < size; len++) {
        for (int left = 0; left < size - len; left++) {
            int right = left + len;
            for (int k = left + 1; k < right; k++) {
                int coins = p[left] * p[k] * p[right]
                          + dp[left][k] + dp[k][right];
                dp[left][right] = Math.max(dp[left][right], coins);
            }
        }
    }
    return dp[0][n + 1];
}
  • Time: O(n
  • Space: O(n
  • Key Insight: Process intervals in order of increasing length. An interval of length L depends only on sub-intervals of length < L. The outer loop over len guarantees all sub-problems are solved before they’re needed.

Recurrence relation:

dp[left][right] = max over k in (left, right) of:
    padded[left] * padded[k] * padded[right]   <- coins for last balloon k
  + dp[left][k]                                <- optimal for left sub-interval
  + dp[k][right]                               <- optimal for right sub-interval

Base case: dp[left][right] = 0  when right - left <= 1 (no balloons to burst)

Trace for [3,1,5,8] → padded = [1,3,1,5,8,1]:

Interval lengths built up:
len=2: dp[0][1]=0, dp[1][2]=0, dp[2][3]=0, dp[3][4]=0, dp[4][5]=0
       (no interior balloons in any length-2 interval)

len=3: dp[0][2]: k=1 → 1*3*1 + 0 + 0 = 3
       dp[1][3]: k=2 → 3*1*5 + 0 + 0 = 15
       dp[2][4]: k=3 → 1*5*8 + 0 + 0 = 40
       dp[3][5]: k=4 → 5*8*1 + 0 + 0 = 40

len=4: dp[0][3]: k=1 → 1*3*5 + 0 + 15 = 30
               k=2 → 1*1*5 + 3 + 0  = 8
               max = 30
       dp[1][4]: k=2 → 3*1*8 + 0 + 40 = 64
               k=3 → 3*5*8 + 15 + 0 = 135
               max = 135
       dp[2][5]: k=3 → 1*5*1 + 0 + 40 = 45
               k=4 → 1*8*1 + 40 + 0 = 48
               max = 48

len=5: dp[0][4]: k=1 → 1*3*8+0+135=159; k=2 → 1*1*8+3+40=51; k=3 → 1*5*8+30+0=70; max=159
       ...

len=6: dp[0][5]: tries all k as last balloon in full array → 167

Answer: dp[0][5] = 167

2D DP Patterns Taxonomy

Grid Traversal DP

Shape: State = (row, col) in a 2D grid.
Movement: Fixed directions (right/down, or all 4).
Problems: Unique Paths (LC 62), Minimum Path Sum (LC 64), Dungeon Game (LC 174), Triangle (LC 120).
Recurrence template: dp[i][j] = f(dp[i-1][j], dp[i][j-1]) — comes from above or from the left.
Space optimization: Always reducible to O(cols) with a rolling row. Column-wise if cols > rows.
Interview signal: “Count paths / min cost to reach (m-1,n-1) moving only right/down.”

Two-Sequence DP

Shape: State = (i, j) = positions in two independent sequences.
Problems: LCS (LC 1143), Edit Distance (LC 72), Interleaving String (LC 97), Distinct Subsequences (LC 115), Shortest Common Supersequence (LC 1092).
Recurrence template:

if s1[i-1] == s2[j-1]: dp[i][j] = combine(dp[i-1][j-1])          // match case
else:                   dp[i][j] = aggregate(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Space optimization: Always reducible to O(min(m,n)) with two-row rolling.
Interview signal: “Given two strings, find something about their relationship (alignment, transformation cost, common structure).”

Interval DP

Shape: State = (left, right) = a range/interval of indices.
Key trick: Think about which operation is LAST within the interval, not first.
Problems: Burst Balloons (LC 312), Matrix Chain Multiplication, Strange Printer (LC 664), Palindrome Partitioning II (LC 132), Minimum Cost Tree From Leaf Values (LC 1130).
Recurrence template:

dp[left][right] = max/min over all k in (left, right) of:
    cost(left, k, right) + dp[left][k] + dp[k][right]

Traversal order: Always process by increasing interval length (outer loop = length).
Time: O(n^3) for 1D range; O(n^6) for 2D range.
Interview signal: “Optimal order to perform operations” or “partition a sequence optimally.”

Knapsack Variations

Shape: State = (item_index, remaining_capacity).
0/1 Knapsack: Each item used at most once → traverse capacity RIGHT TO LEFT in 1D space-opt.
Unbounded Knapsack: Each item used unlimited times → traverse capacity LEFT TO RIGHT.
Problems: Coin Change II (LC 518 — unbounded), 0/1 Knapsack, Partition Equal Subset Sum (LC 416 — 0/1), Target Sum (LC 494).
Recurrence template:

// 0/1 (item i, capacity j)
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

// Unbounded (coin c, amount j)
dp[j] += dp[j - coin]  (left-to-right for combinations)

Combinations vs. permutations:

  • Outer loop = items, inner = amounts → COMBINATIONS (Coin Change II, LC 518)
  • Outer loop = amounts, inner = items → PERMUTATIONS (Combination Sum IV, LC 377)
    Interview signal: “How many ways to make a target using items with a given weight/denomination.”

Key Takeaways

How 2D DP Differs from 1D DP

  • State dimensionality: 1D DP has one “progress” dimension (index into single sequence, or a single capacity). 2D DP has two independent dimensions — both must be tracked simultaneously. If the sub-problem requires knowing your position in TWO things at once, you need 2D.
  • Table filling direction: 1D DP fills left-to-right. 2D DP fills top-to-bottom left-to-right (grid/two-sequence), or by increasing interval length (interval DP). Getting the fill order wrong produces wrong answers.
  • Dependency pattern: In 1D, dp[i] depends on dp[i-1]. In 2D, dp[i][j] typically depends on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] — three predecessors.

Space Optimization: The Rolling Array Technique

  • When applicable: When dp[i][j] depends only on the current row dp[i][...] and the previous row dp[i-1][...]. If it depends on row i-2 or earlier, you need more rows.
  • Two-row pattern (LCS, Edit Distance): Maintain prev[] and curr[]. After filling each row, swap pointers (int[] temp = prev; prev = curr; curr = temp). Reset the reused array to 0.
  • One-row pattern (Unique Paths, Coin Change II): Can collapse to one array when dp[i][j] only needs dp[i-1][j] (same column, previous row) and dp[i][j-1] (left in current row). Direction of traversal (left-to-right vs right-to-left) controls whether current row or previous row values are used.
  • Diagonal dependency: When you need dp[i-1][j-1], save it in a diagPrev variable before overwriting, since the 1D array update will clobber it.

When Interval DP Applies

  • The problem asks for an optimal order of operations on a sequence.
  • Sub-problems are contiguous sub-ranges [i..j] rather than prefixes [0..i].
  • The naive “try all split points” approach has the right structure but exponential cost.
  • Key question: “Can I make sub-problems independent by thinking about which operation happens LAST?” If yes, interval DP applies.
  • Fill order is ALWAYS by increasing interval length — smaller intervals are base cases for larger ones.

Interview Red Flags: When DP Won’t Work

  • No optimal sub-structure: The global optimum cannot be built from sub-problem optima (e.g., longest simple path in a general graph — NP-hard; shortest path works, longest doesn’t).
  • No overlapping sub-problems: If the recursive tree is a pure tree with no repeated states, DP adds overhead without benefit; greedy or divide-and-conquer may be better.
  • State space is exponential: If encoding the state requires a subset of items (not just an index), DP has exponential states (e.g., Travelling Salesman with bitmask DP is O(2^n * n) — acceptable only for n ≤ 20).
  • Output is a path, not a value: Standard DP computes optimal VALUES. Reconstructing the actual path requires backtracking through the filled table or storing parent pointers — add this complexity only if the interviewer asks for it.
  • Confused combinations vs. permutations in knapsack: Outer loop over items = combinations; outer loop over target = permutations. Getting this wrong gives a subtly incorrect answer that passes simple tests but fails on “order matters” cases.

Pattern Recognition Triggers

  • “Two strings, find their alignment / transformation / common structure” → Two-Sequence DP (LCS, Edit Distance)
  • “Count paths in a grid moving only right/down” → Grid DP with rolling row
  • “Count combinations (not permutations) to make a target sum” → Unbounded Knapsack, outer loop = coins
  • “Optimal order to perform operations on a sequence” → Interval DP, think about the LAST operation
  • “Each state’s answer needs position in two things” → The state IS (i, j); build the 2D table

System Design Connections

  • Edit Distance → git diff / spell check: Levenshtein distance with O(n) space optimization is exactly how diff utilities and mobile keyboard autocorrect rank nearest candidates. Production implementations add early termination (stop if distance > threshold) and SIMD-optimized inner loops.
  • LCS → DNA sequence alignment in bioinformatics: BLAST uses a seeded extension of LCS with affine gap penalties (gap-open + gap-extend). The 2D DP table is called the “scoring matrix” in bioinformatics. Smith-Waterman (local alignment) adds a max(0, ...) clamp to the recurrence — identical to how we clamp arm values in tree DP.
  • Interval DP → query plan optimization in databases: Finding the optimal join order in a SQL query with n tables is exactly Matrix Chain Multiplication — an O(n^3) interval DP. PostgreSQL’s optimizer uses dynamic programming for this up to ~8 tables, then switches to genetic algorithms.
  • Coin Change II → financial portfolio construction: Constructing a bond ladder with discrete maturity buckets that sums to a target notional is combinatorially equivalent to Coin Change II. The “combinations not permutations” constraint maps to the fact that holding 3×2yr + 2×5yr is the same portfolio as 2×5yr + 3×2yr.

Graph View

Backlinks