Dynamic Programming Patterns — State, Recurrence and the Main Families

DP is the section people avoid, and the avoidance is a recognition problem rather than a maths one. Every DP solution is a recursion whose subproblems repeat; the technique is noticing the repetition and paying for each subproblem once. Learn the families and most questions become "which one is this".

The four steps

Do these in order, every time. The mistake is trying to write the table first.

State — what arguments distinguish one subproblem from another? dp[i] means

what, exactly, in one sentence?

Recurrence — how does a state's answer follow from smaller ones?
Base cases — the smallest states, answered directly.
Order — memoised recursion (top-down) or a filled table (bottom-up).

Write the brute-force recursion first, then add a cache. That mechanical route gets you to a working solution under pressure far more reliably than trying to see the table.

from functools import cache

def coin_change(coins, amount):
    @cache
    def fewest(remaining):
        if remaining == 0:
            return 0
        if remaining < 0:
            return float("inf")
        return min((1 + fewest(remaining - c) for c in coins), default=float("inf"))

    result = fewest(amount)
    return -1 if result == float("inf") else result

int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, Integer.MIN_VALUE);   // MIN_VALUE = "not computed yet"
    int result = fewest(coins, amount, memo);
    return result >= Integer.MAX_VALUE / 2 ? -1 : result;
}

private int fewest(int[] coins, int remaining, int[] memo) {
    if (remaining == 0) return 0;
    if (remaining < 0) return Integer.MAX_VALUE / 2;   // /2 avoids overflow on +1
    if (memo[remaining] != Integer.MIN_VALUE) return memo[remaining];

    int best = Integer.MAX_VALUE / 2;
    for (int c : coins) {
        best = Math.min(best, 1 + fewest(coins, remaining - c, memo));
    }
    return memo[remaining] = best;
}

int fewest(const vector<int>& coins, int remaining, vector<int>& memo) {
    if (remaining == 0) return 0;
    if (remaining < 0) return INT_MAX / 2;      // /2 avoids overflow on +1
    if (memo[remaining] != INT_MIN) return memo[remaining];

    int best = INT_MAX / 2;
    for (int c : coins) best = min(best, 1 + fewest(coins, remaining - c, memo));
    return memo[remaining] = best;
}

int coinChange(const vector<int>& coins, int amount) {
    vector<int> memo(amount + 1, INT_MIN);
    int result = fewest(coins, amount, memo);
    return result >= INT_MAX / 2 ? -1 : result;
}

/* Bottom-up is simpler in C than threading a memo array through recursion. */
int coinChange(int* coins, int n, int amount) {
    int INF = amount + 1;
    int* dp = malloc((amount + 1) * sizeof(int));
    for (int i = 0; i <= amount; i++) dp[i] = INF;
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int i = 0; i < n; i++) {
            if (coins[i] <= a && dp[a - coins[i]] + 1 < dp[a]) {
                dp[a] = dp[a - coins[i]] + 1;
            }
        }
    }
    int result = dp[amount] >= INF ? -1 : dp[amount];
    free(dp);
    return result;
}

function coinChange(coins, amount) {
  const memo = new Map();

  const fewest = (remaining) => {
    if (remaining === 0) return 0;
    if (remaining < 0) return Infinity;
    if (memo.has(remaining)) return memo.get(remaining);

    let best = Infinity;
    for (const c of coins) best = Math.min(best, 1 + fewest(remaining - c));
    memo.set(remaining, best);
    return best;
  };

  const result = fewest(amount);
  return result === Infinity ? -1 : result;
}

That is the whole method: an obvious recursion, plus one decorator. Converting to a bottom-up table afterwards is a mechanical rewrite and often unnecessary.

The one-dimensional family

dp[i] depends on a constant number of previous entries.

def rob(nums):
    prev = curr = 0
    for x in nums:
        prev, curr = curr, max(curr, prev + x)   # skip this house, or take it
    return curr

int rob(int[] nums) {
    int prev = 0, curr = 0;
    for (int x : nums) {
        int next = Math.max(curr, prev + x);   // skip this house, or take it
        prev = curr;
        curr = next;
    }
    return curr;   // only the last two states matter, so no array is needed
}

int rob(const vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int x : nums) {
        int next = max(curr, prev + x);   // skip this house, or take it
        prev = curr;
        curr = next;
    }
    return curr;   // only the last two states matter
}

int rob(int* nums, int n) {
    int prev = 0, curr = 0;
    for (int i = 0; i < n; i++) {
        int take = prev + nums[i];
        int next = curr > take ? curr : take;   /* skip, or take */
        prev = curr;
        curr = next;
    }
    return curr;
}

function rob(nums) {
  let prev = 0, curr = 0;
  for (const x of nums) {
    [prev, curr] = [curr, Math.max(curr, prev + x)];   // skip, or take
  }
  return curr;   // only the last two states matter, so no array is needed
}

Climbing Stairs, House Robber, Min Cost Climbing Stairs, Decode Ways and Fibonacci are all this shape. Because only the last two states matter, the array collapses to two variables — the standard space optimisation, and the follow-up you will be asked for.

House Robber II (a circle) is the neat one: run the linear solution twice, once excluding

the first house and once excluding the last, and take the better. Recognising that a constraint can be removed by solving two easier instances is a transferable idea.

The knapsack family

Choose a subset subject to a capacity. State is dp[i][capacity].

0/1 — each item used at most once. Iterate capacity downward in the 1-D version.
Unbounded — items reusable. Iterate capacity upward.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2
    reachable = [False] * (target + 1)
    reachable[0] = True

    for x in nums:
        for s in range(target, x - 1, -1):        # DOWNWARD: each item once
            reachable[s] |= reachable[s - x]
    return reachable[target]

boolean canPartition(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    if (total % 2 != 0) return false;

    int target = total / 2;
    boolean[] reachable = new boolean[target + 1];
    reachable[0] = true;

    for (int x : nums) {
        // DOWNWARD is what makes this 0/1 rather than unbounded: it keeps
        // reachable[s - x] referring to the state BEFORE this item.
        for (int s = target; s >= x; s--) {
            reachable[s] |= reachable[s - x];
        }
    }
    return reachable[target];
}

bool canPartition(const vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2) return false;

    int target = total / 2;
    vector<bool> reachable(target + 1, false);
    reachable[0] = true;

    for (int x : nums) {
        // DOWNWARD is what makes this 0/1 rather than unbounded.
        for (int s = target; s >= x; s--) {
            reachable[s] = reachable[s] || reachable[s - x];
        }
    }
    return reachable[target];
}

bool canPartition(int* nums, int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += nums[i];
    if (total % 2) return false;

    int target = total / 2;
    bool* reachable = calloc(target + 1, sizeof(bool));
    reachable[0] = true;

    for (int i = 0; i < n; i++) {
        /* DOWNWARD: each item used at most once */
        for (int s = target; s >= nums[i]; s--) {
            if (reachable[s - nums[i]]) reachable[s] = true;
        }
    }
    bool result = reachable[target];
    free(reachable);
    return result;
}

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2) return false;

  const target = total / 2;
  const reachable = new Array(target + 1).fill(false);
  reachable[0] = true;

  for (const x of nums) {
    // DOWNWARD is what makes this 0/1 rather than unbounded
    for (let s = target; s >= x; s--) {
      reachable[s] = reachable[s] || reachable[s - x];
    }
  }
  return reachable[target];
}

That loop direction is the entire difference between the two variants, and reversing it by accident is the most common DP bug there is. Downward means reachable[s - x] still refers to the state before this item was considered.

Coin Change (unbounded), Coin Change II (counting), Target Sum and Partition Equal Subset Sum are all knapsacks in disguise.

The two-sequence family

Comparing two strings: dp[i][j] covers the first i of one and the first j of the other. Match the characters, or don't.

def longest_common_subsequence(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]       # consume both
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[-1][-1]

int longestCommonSubsequence(String a, String b) {
    // Row and column 0 mean "empty prefix", which removes every boundary case.
    int[][] dp = new int[a.length() + 1][b.length() + 1];

    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a.charAt(i - 1) == b.charAt(j - 1)) {
                dp[i][j] = 1 + dp[i - 1][j - 1];      // consume both
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[a.length()][b.length()];
}

int longestCommonSubsequence(const string& a, const string& b) {
    // Row and column 0 mean "empty prefix", removing every boundary case.
    vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));

    for (size_t i = 1; i <= a.size(); i++) {
        for (size_t j = 1; j <= b.size(); j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[a.size()][b.size()];
}

int longestCommonSubsequence(char* a, char* b) {
    int m = strlen(a), n = strlen(b);
    /* One row at a time: each row depends only on the previous one. */
    int* prev = calloc(n + 1, sizeof(int));
    int* curr = calloc(n + 1, sizeof(int));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) curr[j] = 1 + prev[j - 1];
            else curr[j] = prev[j] > curr[j - 1] ? prev[j] : curr[j - 1];
        }
        int* tmp = prev; prev = curr; curr = tmp;
        memset(curr, 0, (n + 1) * sizeof(int));
    }
    int result = prev[n];
    free(prev); free(curr);
    return result;
}

function longestCommonSubsequence(a, b) {
  // Row and column 0 mean "empty prefix", removing every boundary case.
  const dp = Array.from({ length: a.length + 1 },
                        () => new Array(b.length + 1).fill(0));

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1];  // consume both
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    }
  }
  return dp[a.length][b.length];
}

Characters match → take the diagonal and add one. They do not → take the better of above and left. Row and column zero mean “empty prefix”, which removes every boundary case.

Edit Distance is the same grid with three predecessors instead of two — insert, delete, replace — and Distinct Subsequences, Regular Expression Matching and Wildcard Matching all live on this grid too. The +1 offsets are so that row and column 0 mean "empty prefix", which removes every boundary special case.

The LIS family

dp[i] = the best answer ending at i. Quadratic by default:

def length_of_lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    int[] dp = new int[nums.length];    // dp[i] = best subsequence ENDING at i
    Arrays.fill(dp, 1);

    int best = 1;
    for (int i = 0; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
        }
        best = Math.max(best, dp[i]);
    }
    return best;   // O(n log n) via patience sorting is the follow-up
}

int lengthOfLIS(const vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), 1);   // dp[i] = best subsequence ENDING at i

    int best = 1;
    for (int i = 0; i < (int)nums.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        best = max(best, dp[i]);
    }
    return best;   // O(n log n) via patience sorting is the follow-up
}

int lengthOfLIS(int* nums, int n) {
    if (n == 0) return 0;
    int* dp = malloc(n * sizeof(int));
    int best = 1;

    for (int i = 0; i < n; i++) {
        dp[i] = 1;                      /* best subsequence ENDING at i */
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
        }
        if (dp[i] > best) best = dp[i];
    }
    free(dp);
    return best;
}

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;
  const dp = new Array(nums.length).fill(1);   // dp[i] = best ENDING at i

  let best = 1;
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
    }
    best = Math.max(best, dp[i]);
  }
  return best;   // O(n log n) via patience sorting is the follow-up
}

There is an O(n log n) version using patience sorting and binary search over a "tails" array — worth knowing, because O(n²) invites the follow-up. Maximum Subarray (Kadane's) is the degenerate case where only the immediately preceding state matters.

The interval family

dp[i][j] covers the range i..j, and you iterate by increasing length. Burst Balloons, Matrix Chain Multiplication and Longest Palindromic Substring are here. The reframe that makes Burst Balloons work — think about which balloon is burst last in a range, not first — is the single hardest idea on the sheet, and it is the reason interval DP is worth a separate look.

Complexity

States × work per state. 1-D families are O(n); knapsack is O(n × capacity); two-sequence is O(m × n); interval is O(n³). Space usually reduces by one dimension, because each row depends only on the previous one — say that unprompted.

Mistakes that cost the round

Writing the table before the recurrence. State first, always.
Wrong loop direction in 1-D knapsack, silently turning 0/1 into unbounded.
Sloppy base cases, especially the empty-string row and column.
Memoising on an incomplete state. If the answer depends on something not in the cache

key, the cache returns wrong answers.

Optimising space before it is correct. Get the table right, then collapse it.

What to drill

In this order — each introduces exactly one new idea:

Climbing Stairs → House Robber — 1-D states.
Coin Change → Coin Change II — unbounded knapsack, min then count.
Partition Equal Subset Sum — 0/1 knapsack and the loop direction.
Longest Common Subsequence → Edit Distance — the two-sequence grid.
Longest Increasing Subsequence — ending-at-i states.
Word Break, Unique Paths, Jump Game — the common variants.
Burst Balloons, Regular Expression Matching — interval and hard grid DP.

All 35 are on the 22 DSA Patterns sheet.

Frequently asked

How do I know a problem is dynamic programming?

Two signs together: the problem asks for an optimum or a count over a sequence of choices, and a brute-force recursion would solve the same subproblem repeatedly. If choices are independent and a locally best pick is provably safe, it is greedy instead; if subproblems overlap and a local choice can be wrong, it is DP.

Should I write top-down memoization or bottom-up tabulation?

Top-down first. It is the brute-force recursion plus a cache, so it is far quicker to get right under pressure and it only visits reachable states. Convert to bottom-up when you need the space optimisation or want to avoid recursion depth limits — the rewrite is mechanical once the recurrence is correct.

Why does the loop direction matter in knapsack?

In the space-optimised 1-D version, iterating capacity downward means dp[s - x] still holds the value from before the current item was considered, so each item is used at most once — 0/1 knapsack. Iterating upward lets the item's own update feed back into itself, which is exactly the unbounded variant. One reversed loop silently changes which problem you solved.

Dynamic Programming