Dynamic Programming Cheat Sheet: Patterns, Problems & Solutions

Dynamic programming (DP) breaks a complex problem into overlapping subproblems, solves each once, and stores the result. Master these patterns and you can solve 80% of DP interview questions.

Quick reference

The two approaches

Memoization (top-down)

Recursive + cache. Write the recursion you'd naturally think of, then cache results.

from functools import lru_cache

def fib(n):
    @lru_cache(maxsize=None)
    def dp(i):
        if i <= 1:
            return i
        return dp(i - 1) + dp(i - 2)
    return dp(n)

function fib(n) {
  const memo = new Map();
  function dp(i) {
    if (i <= 1) return i;
    if (memo.has(i)) return memo.get(i);
    const result = dp(i - 1) + dp(i - 2);
    memo.set(i, result);
    return result;
  }
  return dp(n);
}

Tabulation (bottom-up)

Iterative. Fill a table from base cases upward. No recursion overhead.

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Space-optimised (only need last two values):

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Pattern 1 — 1D DP

Climbing stairs (LC 70)

You can climb 1 or 2 steps. How many ways to reach step n?

def climbStairs(n: int) -> int:
    if n <= 2:
        return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

func climbStairs(n int) int {
    if n <= 2 { return n }
    prev2, prev1 := 1, 2
    for i := 3; i <= n; i++ {
        prev2, prev1 = prev1, prev1+prev2
    }
    return prev1
}

Pattern 2 — 2D DP / grid

Minimum path sum (LC 64)

Grid of non-negative numbers. Find path from top-left to bottom-right with minimum sum (right or down only).

def minPathSum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [row[:] for row in grid]  # copy
    for i in range(1, m):
        dp[i][0] += dp[i-1][0]
    for j in range(1, n):
        dp[0][j] += dp[0][j-1]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] += min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]

function minPathSum(grid) {
  const m = grid.length, n = grid[0].length;
  const dp = grid.map(row => [...row]);
  for (let i = 1; i < m; i++) dp[i][0] += dp[i-1][0];
  for (let j = 1; j < n; j++) dp[0][j] += dp[0][j-1];
  for (let i = 1; i < m; i++)
    for (let j = 1; j < n; j++)
      dp[i][j] += Math.min(dp[i-1][j], dp[i][j-1]);
  return dp[m-1][n-1];
}

Pattern 3 — 0/1 Knapsack

Each item can be used at most once. State: dp[i][w] = max value using first i items with capacity w.

def knapsack(weights: list, values: list, capacity: int) -> int:
    n = len(weights)
    # 1D optimised — iterate weights in reverse
    dp = [0] * (capacity + 1)
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

func knapsack(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    for i := range weights {
        for w := capacity; w >= weights[i]; w-- {
            if dp[w-weights[i]]+values[i] > dp[w] {
                dp[w] = dp[w-weights[i]] + values[i]
            }
        }
    }
    return dp[capacity]
}

Key: reverse inner loop prevents using the same item twice.

Subset sum (LC 416)

Can we partition array into two equal-sum subsets?

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

Pattern 4 — Unbounded Knapsack

Each item can be used unlimited times. Inner loop goes forward.

Coin change (LC 322)

Minimum coins to make amount.

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for a in range(coin, amount + 1):   # forward = unbounded
            dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (const coin of coins)
    for (let a = coin; a <= amount; a++)
      dp[a] = Math.min(dp[a], dp[a - coin] + 1);
  return dp[amount] === Infinity ? -1 : dp[amount];
}

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);
    dp[0] = 0;
    for (int coin : coins)
        for (int a = coin; a <= amount; a++)
            dp[a] = Math.min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

Coin change II — number of ways (LC 518)

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for a in range(coin, amount + 1):
            dp[a] += dp[a - coin]
    return dp[amount]

Pattern 5 — Longest Common Subsequence (LCS)

dp[i][j] = LCS length for s1[:i] and s2[:j].

def longestCommonSubsequence(s1: str, s2: str) -> int:
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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]

func longestCommonSubsequence(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp { dp[i] = make([]int, n+1) }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else if dp[i-1][j] > dp[i][j-1] {
                dp[i][j] = dp[i-1][j]
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[m][n]
}

Edit distance (LC 72)

Minimum operations (insert/delete/replace) to convert word1 to word2.

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j-1])
            prev = temp
    return dp[n]

Pattern 6 — Longest Increasing Subsequence (LIS)

O(n²) DP:

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

O(n log n) patience sorting:

import bisect

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

function lengthOfLIS(nums) {
  const tails = [];
  for (const num of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (tails[mid] < num) lo = mid + 1;
      else hi = mid;
    }
    tails[lo] = num;
  }
  return tails.length;
}

Pattern 7 — DP on intervals

For problems of the form "what's the optimal way to split/merge a range [i, j]?"

Matrix chain multiplication

Minimum scalar multiplications to multiply a chain of matrices.

def matrixChain(dims: list[int]) -> int:
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    # length = number of matrices in subchain
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

Burst balloons (LC 312)

def maxCoins(nums: list[int]) -> int:
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):
        for left in range(0, n - length):
            right = left + length
            for k in range(left + 1, right):
                dp[left][right] = max(
                    dp[left][right],
                    nums[left] * nums[k] * nums[right]
                    + dp[left][k] + dp[k][right]
                )
    return dp[0][n-1]

Pattern 8 — DP on trees

Post-order traversal: solve children first, then the current node.

House robber III (LC 337)

Rob houses in a binary tree — no two adjacent nodes.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def rob(root: TreeNode) -> int:
    def dp(node):
        if not node:
            return 0, 0  # (rob_this, skip_this)
        left_rob, left_skip = dp(node.left)
        right_rob, right_skip = dp(node.right)
        rob_this = node.val + left_skip + right_skip
        skip_this = max(left_rob, left_skip) + max(right_rob, right_skip)
        return rob_this, skip_this
    return max(dp(root))

Pattern 9 — Bitmask DP

State = bitmask of which items have been used. Useful when n ≤ 20.

Travelling Salesman Problem (TSP)

Minimum cost tour visiting all cities exactly once.

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float('inf')
    # dp[mask][i] = min cost to reach city i, having visited cities in mask
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0 (bit 0 set)
    for mask in range(1 << n):
        for u in range(n):
            if dp[mask][u] == INF:
                continue
            if not (mask >> u & 1):
                continue
            for v in range(n):
                if mask >> v & 1:
                    continue  # already visited
                new_mask = mask | (1 << v)
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
    return min(dp[(1 << n) - 1][i] + dist[i][0] for i in range(n))

Classic problems quick reference

How to identify a DP problem

1. "Count the number of ways" → often DP
2. "Minimum/maximum cost/length" → optimisation DP
3. "Can you achieve X?" → feasibility DP (boolean)
4. Overlapping subproblems: naïve recursion revisits the same state → cache it
5. Optimal substructure: optimal solution to the problem includes optimal solutions to subproblems

Not DP if subproblems are independent (divide-and-conquer like merge sort).

DP problem-solving framework

1. Define the state
   - What information do I need to characterise a subproblem?
   - dp[i], dp[i][j], dp[mask][i], dp[i][j][k]?

2. Write the recurrence
   - How does dp[i] depend on smaller subproblems?
   - Draw a small example (n=3 or 4) and trace it.

3. Identify base cases
   - dp[0] = ?, dp[0][0] = ?

4. Decide iteration order
   - Bottom-up: make sure dp[i-1] is computed before dp[i]

5. Extract the answer
   - Often dp[n], dp[m][n], max(dp), or dp[(1<<n)-1][start]

Common mistakes

DP complexity guide

FAQ

Q: Memoization or tabulation — which to use?
Start with memoization (easier to write). Switch to tabulation if you hit recursion depth limits or need to optimise space.

Q: How do I reduce 2D DP to 1D?
If dp[i][j] only depends on row i-1, you can keep just one row and update it in the right order (forward or backward depending on the pattern).

Q: What's the difference between DP and divide-and-conquer?
D&C subproblems are independent. DP subproblems overlap — the same subproblem appears in multiple branches. Caching that overlap is the whole point.

Q: How do I handle DP with negative indices?
Add an offset. If index range is [-n, n], shift by n so you use dp[i+n].

Q: When should I use bitmask DP?
When the state is a subset of items, typically n ≤ 20 (2²⁰ = 1 million states). Common in assignment problems, TSP, and shortest Hamiltonian path.

Q: What's Kadane's algorithm?
A special O(n) 1D DP for maximum subarray sum: dp[i] = max(nums[i], dp[i-1] + nums[i]). Since you only need the previous state, you keep just one variable: cur_max = max(num, cur_max + num).