DSA · Lesson 15 of 17

Dynamic Programming (2-D)

⏱ 15 min🎬 Interactive visualizer💻 Python · Java · C++ · JavaScript🧩 6 practice problems

Tables indexed by two things: two strings (LCS, edit distance), a grid (paths), or items × capacity (knapsack). Watch every cell get filled.

When you need two dimensions

The state needs two numbers when the subproblem depends on two moving parts:

Two strings: dp[i][j] = answer for the first i characters of A and the first j of B (LCS, edit distance, distinct subsequences, interleaving strings)
A grid: dp[r][c] = answer at cell (r, c) (unique paths, minimum path sum, maximal square)
Items × budget: dp[i][w] = best value using the first i items with capacity w (0/1 knapsack, subset sum, partition, target sum)
Intervals: dp[l][r] = answer for the substring or subarray l..r (longest palindromic subsequence, burst balloons, matrix-chain)

Reading a 2-D recurrence

Each cell looks at a few neighbours that are already filled: up dp[i−1][j], left dp[i][j−1], and the diagonal dp[i−1][j−1]. Fill row by row so those neighbours are ready.

Problem	Match / take	Otherwise
LCS	diagonal + 1	max(up, left)
Edit distance	diagonal	1 + min(up = delete, left = insert, diagonal = replace)
Unique paths		up + left
0/1 knapsack	up-left by weight + value	up (skip the item)

Space optimisation

When row i only needs row i − 1, keep one or two rows. In 0/1 knapsack with a single 1-D array, loop the capacity downwards so each item is used at most once; loop upwards for unlimited reuse (coin change, unbounded knapsack).

Code template

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

def knapsack(weights, values, cap):        # 0/1: each item once
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):    # downwards!
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

int lcs(String a, String b) {
    int m = a.length(), n = b.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a.charAt(i - 1) == b.charAt(j - 1) ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

int knapsack(int[] w, int[] v, int cap) {          // 0/1: each item once
    int[] dp = new int[cap + 1];
    for (int i = 0; i < w.length; i++)
        for (int c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);   // downwards!
    return dp[cap];
}

int lcs(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = a[i - 1] == b[j - 1] ? dp[i - 1][j - 1] + 1 : max(dp[i - 1][j], dp[i][j - 1]);
    return dp[m][n];
}

int knapsack(const vector<int>& w, const vector<int>& v, int cap) {   // 0/1
    vector<int> dp(cap + 1, 0);
    for (size_t i = 0; i < w.size(); i++)
        for (int c = cap; c >= w[i]; c--) dp[c] = max(dp[c], dp[c - w[i]] + v[i]);   // downwards!
    return dp[cap];
}

function lcs(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++)
    for (let j = 1; j <= n; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1]);
  return dp[m][n];
}

function knapsack(w, v, cap) {             // 0/1: each item once
  const dp = new Array(cap + 1).fill(0);
  for (let i = 0; i < w.length; i++)
    for (let c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]); // downwards!
  return dp[cap];
}

Practise this pattern (6 problems)

Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.

#	Problem	Difficulty
77	Unique Paths	Medium
78	Longest Common Subsequence	Medium
79	Edit Distance	Medium
80	0/1 Knapsack	Medium
81	Partition Equal Subset Sum	Medium
82	Minimum Path Sum	Medium

Common mistakes

Off-by-one errors between string indices and dp indices: dp[i][j] uses A[i−1] and B[j−1].
Missing base row or column (the empty prefix).
In 1-D knapsack, looping capacity upwards, which silently turns 0/1 into unbounded.

Check yourself: what is the LCS of “abcde” and “ace”, and which cells give +1?

“ace”, length 3. The diagonal +1 happens at the matching pairs (a, a), (c, c) and (e, e).

🧩 All DSA problems 🎬 Algorithm visualizer 🎓 Certificates

Created by Ajeetkumar