Dynamic Programming Patterns: Knapsack, LCS, LIS, Grid & Intervals

Dynamic programming (DP) solves a problem by breaking it into overlapping subproblems with optimal substructure, computing each subproblem once and reusing the result. The hard part isn’t the caching — it’s recognizing which of a handful of recurring DP shapes a problem fits. This page recaps the major DP sub-patterns, the signal for each, and gives a reusable template for the most common one.

For the topic foundations, see dynamic programming: introduction and memoization vs tabulation.

The signal: is it DP at all?

DP applies when both hold:

Optimal substructure — the best answer is built from best answers to smaller subproblems.
Overlapping subproblems — the same subproblem is solved many times by naive recursion.

Trigger phrases: “count the number of ways,” “minimum / maximum cost/length/value,” “can you reach / make / partition,” and “best over a sequence of choices” where greedy fails and the subproblems repeat. If you’d generate every arrangement instead, that’s backtracking, not DP.

The DP sub-patterns at a glance

Sub-pattern	Signal	State	Topic page
0/1 Knapsack	Pick items under a capacity; each item in or out	`dp[i][w]`	Knapsack
Unbounded / Coin Change	Reuse items unlimited times; “ways” or “min coins”	`dp[amount]`	Coin Change
LCS (two sequences)	Compare two strings/arrays; common/edit/match	`dp[i][j]`	LCS, Edit Distance
LIS (one sequence)	Increasing/decreasing subsequence in one array	`dp[i]`	LIS
Grid DP	Paths/cost through an `m × n` grid	`dp[r][c]`	DP on Grids
Interval DP	Best way to combine/cut a range `[i, j]`	`dp[i][j]`	DP on Subsequences

Template: 0/1 knapsack (the archetype)

Most “pick a subset under a limit” DPs reduce to this. For each item you choose include-or-exclude; dp[w] is the best value achievable with capacity w. The 1-D rolling array iterates capacity downward so each item is used at most once.

#include <vector>
#include <algorithm>
// 0/1 knapsack: max value with total weight <= capacity. O(n*capacity).
int knapsack(const std::vector<int>& weight, const std::vector<int>& value, int capacity) {
    std::vector<int> dp(capacity + 1, 0);          // dp[w] = best value for capacity w
    for (int i = 0; i < (int)weight.size(); i++)
        for (int w = capacity; w >= weight[i]; w--)   // iterate downward: each item once
            dp[w] = std::max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[capacity];
}

// 0/1 knapsack: max value with total weight <= capacity. O(n*capacity).
int knapsack(int[] weight, int[] value, int capacity) {
    int[] dp = new int[capacity + 1];              // dp[w] = best value for capacity w
    for (int i = 0; i < weight.length; i++)
        for (int w = capacity; w >= weight[i]; w--)   // iterate downward: each item once
            dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
    return dp[capacity];
}

// 0/1 knapsack: max value with total weight <= capacity. O(n*capacity).
function knapsack(weight, value, capacity) {
  const dp = new Array(capacity + 1).fill(0);      // dp[w] = best value for capacity w
  for (let i = 0; i < weight.length; i++)
    for (let w = capacity; w >= weight[i]; w--)     // iterate downward: each item once
      dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
  return dp[capacity];
}

# 0/1 knapsack: max value with total weight <= capacity. O(n*capacity).
def knapsack(weight, value, capacity):
    dp = [0] * (capacity + 1)              # dp[w] = best value for capacity w
    for i in range(len(weight)):
        for w in range(capacity, weight[i] - 1, -1):  # downward: each item once
            dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
    return dp[capacity]

Template: longest common subsequence (two-sequence DP)

The two-string archetype. dp[i][j] is the LCS length of the first i chars of a and first j of b. Edit distance, shortest common supersequence, and many string DPs are variations of this grid fill.

#include <string>
#include <vector>
#include <algorithm>
// Longest common subsequence length. O(n*m).
int lcs(const std::string& a, const std::string& b) {
    int n = a.size(), m = b.size();
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a[i-1] == b[j-1])
                ? dp[i-1][j-1] + 1                       // match: extend diagonal
                : std::max(dp[i-1][j], dp[i][j-1]);      // skip one char
    return dp[n][m];
}

// Longest common subsequence length. O(n*m).
int lcs(String a, String b) {
    int n = a.length(), m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = (a.charAt(i-1) == b.charAt(j-1))
                ? dp[i-1][j-1] + 1                       // match: extend diagonal
                : Math.max(dp[i-1][j], dp[i][j-1]);      // skip one char
    return dp[n][m];
}

// Longest common subsequence length. O(n*m).
function lcs(a, b) {
  const n = a.length, m = b.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let j = 1; j <= m; j++)
      dp[i][j] = (a[i-1] === b[j-1])
        ? dp[i-1][j-1] + 1                              // match: extend diagonal
        : Math.max(dp[i-1][j], dp[i][j-1]);             // skip one char
  return dp[n][m];
}

# Longest common subsequence length. O(n*m).
def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1             # match: extend diagonal
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # skip one char
    return dp[n][m]

The other sub-patterns in one line each

LIS — dp[i] = longest increasing subsequence ending at i; O(n²), or O(n log n) with a patience-sort/binary-search variant. See longest increasing subsequence.
Grid DP — dp[r][c] from dp[r-1][c] and dp[r][c-1]; min-path-sum and unique-paths. See DP on grids.
Interval DP — dp[i][j] over a range, trying every split point k between i and j (matrix-chain, burst balloons). See DP on subsequences & strings.
1-D sequence DP — Fibonacci, climbing stairs, house robber; dp[i] from a few previous states. See Fibonacci & climbing stairs.

How to attack any DP problem

Define the state — what do the indices of dp mean? (This is 80% of the work.)
Write the recurrence — express dp[state] in terms of smaller states.
Set base cases — the smallest subproblems.
Choose the order — top-down memoization or bottom-up tabulation.
Optimize space if only the last row/column is needed (as the knapsack 1-D array shows).

For beginners: Start by writing the plain recursion (this is backtracking). If you notice the same arguments recurring, add a cache — that’s memoization, and you’ve just done DP.

Complexity

DP cost is usually (number of states) × (work per state). Knapsack and LCS are both O(n·m) time; LCS uses O(n·m) space (reducible to O(min(n, m))), and the 1-D knapsack uses O(capacity) space. Interval DP is typically O(n³) (a split loop inside a 2-D table).

Practice

Drill all five sub-patterns in the dynamic programming exercises. When you can name the sub-pattern from the problem statement alone, DP stops being scary. Back to the patterns overview.