36  Algorithm Design — Dynamic Programming II (Strings & Grids)

37 Algorithm Design — DP II

Week 7, Session 2. CSS 343.

37.1 Warmup

Unique Paths (#62). A robot on an m×n grid starts at top-left, ends at bottom-right, can only move right or down. How many distinct paths?

class Solution {
 public:
  int uniquePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 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];
  }
};

Each cell counts paths to reach it: either from above or from the left. Two-dimensional DP. O(mn).

37.2 Learning objectives

  1. Define the LCS subproblem and fill the DP table.
  2. Trace back through the LCS table to recover the subsequence.
  3. Implement edit distance with the three-operation recurrence.
  4. Solve Unique Paths by recognizing it as a combinatorial DP.
  5. Describe how LCS and edit distance power real tools (diff, spell checkers, Git).

37.3 Longest Common Subsequence (LCS)

Given two strings, find the longest sequence of characters appearing in both (not necessarily contiguous, but in order).

LCS(“ABCB”, “BCB”) = “BCB” of length 3. LCS(“AGGTAB”, “GXTXAYB”) = “GTAB” of length 4.

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

Recurrence:

\[ dp[i][j] = \begin{cases} 0 & \text{if } i = 0 \text{ or } j = 0 \\ dp[i-1][j-1] + 1 & \text{if } s_1[i-1] = s_2[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases} \]

int lcs(const string& s1, const string& s2) {
  int m = s1.size(), n = s2.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) {
      if (s1[i-1] == s2[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];
}

37.3.1 Traceback — recover the subsequence

The DP table tells you the length. To find the actual subsequence, walk backwards from dp[m][n]:

string lcsString(const string& s1, const string& s2) {
  int m = s1.size(), n = s2.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) {
      if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
      else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
  }
  string result;
  int i = m, j = n;
  while (i > 0 && j > 0) {
    if (s1[i-1] == s2[j-1]) {
      result.push_back(s1[i-1]);
      --i; --j;
    } else if (dp[i-1][j] > dp[i][j-1]) {
      --i;
    } else {
      --j;
    }
  }
  reverse(result.begin(), result.end());
  return result;
}

37.4 Edit Distance (Levenshtein)

Minimum number of single-character edits (insert, delete, replace) to convert s1 into s2.

int editDistance(const string& s1, const string& s2) {
  int m = s1.size(), n = s2.size();
  vector<vector<int>> dp(m + 1, vector<int>(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 (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
      else dp[i][j] = 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
    }
  }
  return dp[m][n];
}

Three options at each non-match: replace (dp[i-1][j-1]), delete from s1 (dp[i-1][j]), insert into s1 (dp[i][j-1]). Take the cheapest plus one for the operation.

editDistance("kitten", "sitting") = 3. Replace k→s, replace e→i, insert g.

37.5 Longest Increasing Subsequence (LIS)

LIS (#300). Longest strictly increasing subsequence.

O(n²) DP:

int lengthOfLIS_n2(vector<int>& nums) {
  int n = nums.size();
  vector<int> dp(n, 1);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
      if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
    }
  }
  return *max_element(dp.begin(), dp.end());
}

O(n log n) — patience sorting:

int lengthOfLIS(vector<int>& nums) {
  vector<int> tails;
  for (int x : nums) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) tails.push_back(x);
    else *it = x;
  }
  return tails.size();
}

tails is not the actual LIS — it is a clever invariant. The length of tails equals the length of the LIS. The trick: each tails[i] is the smallest tail value of any increasing subsequence of length i+1 seen so far. This is the patience-card-game algorithm.

37.6 Real-world hooks

  • Unix diff uses LCS to find the longest common run between two files; everything else is added or deleted.
  • Spell checkers use edit distance to suggest near-words.
  • Git uses both for merging.
  • Bioinformatics: sequence alignment is a generalized edit distance.

37.7 Try it

Implement lcs("ABCBDAB", "BDCABA"). Length should be 4 (e.g., “BCBA” or “BDAB”). Verify by tracing the DP table.

37.8 Self-check

1. LCS DP space complexity (without traceback) can be reduced to:
b. Each row depends only on the previous row, so two rows suffice. For traceback, you need the full table.
2. Edit distance recurrence at a non-match takes min of three options. The three operations they correspond to are:
c. dp[i-1][j-1] = replace; dp[i-1][j] = delete from s1; dp[i][j-1] = insert into s1.

37.9 Challenges

  1. Longest Common Subsequence (#1143).
  2. Edit Distance (#72).
  3. Longest Increasing Subsequence (#300).
  4. Unique Paths II (#63) — same DP with obstacles.
  5. Word Break (#139) — DP with a dictionary.

37.10 Where this fits

DP done. The remaining chapters are about organizing the code we have been writing — OOP design — and understanding what is computable. Different flavor of CS.

You are here Coming up
2D DP on strings/grids, LCS, edit distance, LIS Chapter 35: OOP design patterns