DP on Subsequences & Strings: Patterns Recap

This page ties together the subsequence and string DP patterns from the rest of the course. Most of these problems reduce to a small handful of templates: take-or-skip over one sequence, two-pointer 2D DP over two sequences, and interval/palindrome DP within one string. Recognizing which template fits is the real skill — once you do, the recurrence is almost mechanical.

Pattern 1: Take-or-skip over one sequence

When each element offers a binary choice (include it or not) under some constraint, define dp over (index, accumulated-constraint). This is the shape of 0/1 knapsack and subset sum: can any subset hit a target sum?

State: dp[i][s] = can the first i numbers form sum s?
Transition: dp[i][s] = dp[i-1][s] || dp[i-1][s - num] (skip or take).
Base case: dp[0][0] = true.

bool subsetSum(const std::vector<int>& nums, int target) {
    std::vector<char> dp(target + 1, false);
    dp[0] = true;
    for (int x : nums)
        for (int s = target; s >= x; s--)        // reverse: each number once
            dp[s] = dp[s] || dp[s - x];
    return dp[target];
}

boolean subsetSum(int[] nums, int target) {
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int x : nums)
        for (int s = target; s >= x; s--)        // reverse: each number once
            dp[s] = dp[s] || dp[s - x];
    return dp[target];
}

function subsetSum(nums, target) {
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of nums)
    for (let s = target; s >= x; s--)            // reverse: each number once
      dp[s] = dp[s] || dp[s - x];
  return dp[target];
}

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):       # reverse: each number once
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

Pattern 2: Two-pointer 2D DP over two sequences

When the answer depends on comparing two strings/arrays, use dp[i][j] indexed by a prefix of each, and branch on whether the current characters match. This is Longest Common Subsequence, edit distance, and string-matching/regex problems.

The mental template:

if (a[i-1] == b[j-1])  dp[i][j] = f(dp[i-1][j-1])      // characters align
else                   dp[i][j] = g(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Whether f/g use +1, max, or min depends on whether you count, maximize, or minimize.

Pattern 3: Interval / palindrome DP within one string

Some problems consider substrings (i..j ranges). Palindrome DP is the classic: dp[i][j] is true when s[i..j] is a palindrome. The transition shrinks the interval from both ends.

State: dp[i][j] = is s[i..j] a palindrome?
Transition: dp[i][j] = (s[i] == s[j]) && (j - i < 2 || dp[i+1][j-1]).
Order: iterate i descending (or by increasing length) so dp[i+1][...] is ready.

std::string longestPalindrome(const std::string& s) {
    int n = s.size();
    if (n == 0) return "";
    std::vector<std::vector<char>> dp(n, std::vector<char>(n, false));
    int start = 0, best = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            if (s[i] == s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > best) { best = j - i + 1; start = i; }
            }
    return s.substr(start, best);
}

String longestPalindrome(String s) {
    int n = s.length();
    if (n == 0) return "";
    boolean[][] dp = new boolean[n][n];
    int start = 0, best = 1;
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            if (s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > best) { best = j - i + 1; start = i; }
            }
    return s.substring(start, start + best);
}

function longestPalindrome(s) {
  const n = s.length;
  if (n === 0) return "";
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0, best = 1;
  for (let i = n - 1; i >= 0; i--)
    for (let j = i; j < n; j++)
      if (s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1])) {
        dp[i][j] = true;
        if (j - i + 1 > best) { best = j - i + 1; start = i; }
      }
  return s.substring(start, start + best);
}

def longest_palindrome(s):
    n = len(s)
    if n == 0:
        return ""
    dp = [[False] * n for _ in range(n)]
    start, best = 0, 1
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i < 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if j - i + 1 > best:
                    best, start = j - i + 1, i
    return s[start:start + best]

How to recognize the pattern

Clue in the problem	Likely pattern	Example
”subset / pick some elements to hit a target”	take-or-skip	knapsack, subset sum
”two strings/arrays compared”	2D two-pointer	LCS, edit distance
”longest/contiguous within one string”	interval/palindrome	longest palindromic substring
”ways/min over linear choices”	1D linear DP	climbing stairs, coin change
”ending at index i”	per-index DP	LIS

For beginners: Don’t memorize 30 problems — memorize these 5 shapes and the question each dp cell answers. New problems are almost always a remix of a template you already know.

Going deeper: The hardest step is choosing the state. Ask: “What’s the smallest set of parameters that fully describes a subproblem?” If two different paths reach the same parameters with the same future, they share a state — and that’s where caching pays off.

Ready to apply all of this? Head to the DP exercises and check your work on the solutions page.