Skip to main content

Sequence and Grid DP Workshop

Retrieval Prompts​

  1. Write the O(n^2) LIS recurrence from memory.
  2. Write the edit-distance recurrence dp[i][j] with all three transitions and base cases.
  3. Write the 0/1 knapsack recurrence, and state the descending/ascending loop-direction trick.
  4. Write the right-or-down grid-path-count recurrence and its base cases.
  5. Describe how the O(n log n) LIS tails array works and why it is not itself an LIS.

Compare and Distinguish​

Separate these pairs clearly:

  • LIS O(n^2) versus O(n log n) (same problem, different state design)
  • edit distance versus longest common subsequence (min operations vs count of matches)
  • 0/1 knapsack versus unbounded knapsack (descending vs ascending loop direction)
  • grid path count versus grid min-cost path (same shape, different operation: + vs min)

Common Mistake Check​

For each statement, identify the error:

  1. "In O(n log n) LIS, tails at the end is one valid LIS."
  2. "For 0/1 knapsack with a rolled array, you can iterate capacity in ascending order."
  3. "Edit distance base case is dp[0][j] = 0 because the empty string matches anything."
  4. "For strictly increasing LIS the binary search uses >, and for non-decreasing it uses >=." (hint: double-check both halves)
  5. "Rolling-array space reduction works even when you need reconstruction."

Mini Application​

For each task, write the state definition, recurrence, complexity, and a 6- to 10-line pseudocode. Then verify with a small hand-traced example.

  1. Given an array a[1..n], compute the length and one actual LIS in O(n^2).
  2. Given strings s and t, compute the edit distance and one minimum-cost edit script.
  3. Given items with (w, v) and capacity W, compute the max value and one list of chosen items (0/1).
  4. Given an m x n grid with obstacles (1 = blocked), count paths from (0, 0) to (m-1, n-1) moving only right or down. Answer modulo 10^9 + 7.
  5. (Stretch) Given s of length n, compute the longest palindromic subsequence of s. Hint: reduce to LCS of s and reverse(s).

Evidence Check​

This page is complete only if you have working (even small) implementations of LIS, edit distance with reconstruction, 0/1 knapsack with reconstruction, and grid path count with obstacles, and you can explain the trade-offs of each versus its rolled-array space-reduced version.