Dynamic Programming Interview Patterns

From Recursion → Memoization → Tabulation → Space Optimization

Dynamic Programming becomes much easier when you stop memorizing dp[] formulas and instead learn how to derive them.

Most DP problems follow the same progression:

Problem
   ↓
Identify choices
   ↓
Write recursion
   ↓
Find repeated states
   ↓
Add memoization
   ↓
Convert recursion to tabulation
   ↓
Optimize space

This guide focuses on the most common DP patterns and the problems that belong to them.

The goal is not to memorize every solution.

The goal is:

See a new problem → identify its pattern → derive the DP from recursion.

1. The Universal DP Process

Before learning individual patterns, understand this process.

Suppose we have:

def solve(state):
    ...

python

The recursive function represents:

"What is the answer to the remaining problem from this state?"

If there are multiple choices:

                state
               /     \
          choice 1   choice 2
              ↓         ↓
           state A    state B

we calculate both and combine them.

For example:

def solve(i):
 
    take = ...
    skip = ...
 
    return max(take, skip)

python

If the same state is reached multiple times, recursion becomes expensive.

We cache it:

@lru_cache(None)
def solve(i):
    ...

python

Now convert the recursive state directly into a DP table.

If recursion is:

solve(i)

python

we usually get:

dp[i]

python

If recursion is:

solve(i, j)

python

we usually get:

dp[i][j]

python

If recursion is:

solve(i, capacity)

python

we usually get:

dp[i][capacity]

python

This is the key idea:

The parameters of your recursive function usually become the dimensions of your DP table.

2. Pattern 1 — 1D / Linear DP

When to recognize it

Look for:

arrays or strings
decisions moving from left to right
current answer depends on previous/future positions
maximum/minimum/count
"ways to reach..."
"best answer starting from index i"

Typical problems:

Climbing Stairs
Min Cost Climbing Stairs
House Robber
House Robber II
Decode Ways
Word Break

Problem 1: Climbing Stairs

You can climb either:

1 step
2 steps

Find the number of ways to reach step n.

Recursive

At step n, the previous step was either:

n - 1
OR
n - 2

def climbStairs(n):
 
    def solve(i):
 
        if i == 0:
            return 1
 
        if i < 0:
            return 0
 
        return (
            solve(i - 1)
            + solve(i - 2)
        )
 
    return solve(n)

python

Memoized

The recursive state is:

so we cache i.

from functools import lru_cache
 
def climbStairs(n):
 
    @lru_cache(None)
    def solve(i):
 
        if i == 0:
            return 1
 
        if i < 0:
            return 0
 
        return (
            solve(i - 1)
            + solve(i - 2)
        )
 
    return solve(n)

python

Bottom-Up

The recursion says:

solve(i)
    ↓
solve(i-1)
solve(i-2)

Therefore:

dp[i]
    ↓
dp[i-1]
dp[i-2]

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

python

Space Optimized

Only the previous two values are needed.

def climbStairs(n):
 
    prev2 = 1
    prev1 = 1
 
    for _ in range(n):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
 
    return prev2

python

Problem 2: House Robber

At every house:

Rob
OR
Skip

If you rob house i, you cannot rob i + 1.

Recursive

def rob(nums):
 
    def solve(i):
 
        if i >= len(nums):
            return 0
 
        take = nums[i] + solve(i + 2)
        skip = solve(i + 1)
 
        return max(take, skip)
 
    return solve(0)

python

Memoized

from functools import lru_cache
 
def rob(nums):
 
    @lru_cache(None)
    def solve(i):
 
        if i >= len(nums):
            return 0
 
        take = nums[i] + solve(i + 2)
        skip = solve(i + 1)
 
        return max(take, skip)
 
    return solve(0)

python

Bottom-Up

The recursion depends on:

solve(i+1)
solve(i+2)

Therefore:

def rob(nums):
 
    n = len(nums)
 
    dp = [0] * (n + 2)
 
    for i in range(n - 1, -1, -1):
 
        dp[i] = max(
            nums[i] + dp[i + 2],
            dp[i + 1]
        )
 
    return dp[0]

python

Space Optimized

def rob(nums):
 
    next1 = 0
    next2 = 0
 
    for money in reversed(nums):
 
        curr = max(
            money + next2,
            next1
        )
 
        next2 = next1
        next1 = curr
 
    return next1

python

Problem 3: House Robber II

The houses form a circle.

Therefore, we cannot rob both:

first
AND
last

Split into two linear problems:

Case 1: nums[0:-1]
Case 2: nums[1:]

def rob(nums):
 
    if len(nums) == 1:
        return nums[0]
 
    def rob_linear(arr):
 
        prev2 = 0
        prev1 = 0
 
        for money in arr:
 
            curr = max(
                prev1,
                prev2 + money
            )
 
            prev2 = prev1
            prev1 = curr
 
        return prev1
 
    return max(
        rob_linear(nums[:-1]),
        rob_linear(nums[1:])
    )

python

Problem 4: Decode Ways

At every position:

Decode one digit
OR
Decode two digits

Recursive state:

i = current position

def numDecodings(s):
 
    def solve(i):
 
        if i == len(s):
            return 1
 
        if s[i] == '0':
            return 0
 
        answer = solve(i + 1)
 
        if (
            i + 1 < len(s)
            and 10 <= int(s[i:i + 2]) <= 26
        ):
            answer += solve(i + 2)
 
        return answer
 
    return solve(0)

python

Memoization:

from functools import lru_cache
 
def numDecodings(s):
 
    @lru_cache(None)
    def solve(i):
 
        if i == len(s):
            return 1
 
        if s[i] == '0':
            return 0
 
        answer = solve(i + 1)
 
        if (
            i + 1 < len(s)
            and 10 <= int(s[i:i + 2]) <= 26
        ):
            answer += solve(i + 2)
 
        return answer
 
    return solve(0)

python

Bottom-up:

def numDecodings(s):
 
    n = len(s)
 
    dp = [0] * (n + 1)
 
    dp[n] = 1
 
    for i in range(n - 1, -1, -1):
 
        if s[i] == '0':
            continue
 
        dp[i] = dp[i + 1]
 
        if (
            i + 1 < n
            and 10 <= int(s[i:i + 2]) <= 26
        ):
            dp[i] += dp[i + 2]
 
    return dp[0]

python

3. Pattern 2 — 0/1 Knapsack

Recognition

Think:

Take or don't take, and each item can be used once.

Common problems:

0/1 Knapsack
Subset Sum
Equal Sum Partition
Count Subsets
Minimum Subset Sum Difference
Target Sum

The state usually contains:

item index
+
capacity/target

Problem 5: 0/1 Knapsack

Recursive

def knapsack(weights, values, capacity):
 
    def solve(i, remaining):
 
        if i == len(weights) or remaining == 0:
            return 0
 
        skip = solve(i + 1, remaining)
 
        take = 0
 
        if weights[i] <= remaining:
            take = (
                values[i]
                + solve(
                    i + 1,
                    remaining - weights[i]
                )
            )
 
        return max(take, skip)
 
    return solve(0, capacity)

python

Notice:

i + 1

python

after taking an item.

That means the item cannot be used again.

Memoized

from functools import lru_cache
 
def knapsack(weights, values, capacity):
 
    @lru_cache(None)
    def solve(i, remaining):
 
        if i == len(weights) or remaining == 0:
            return 0
 
        skip = solve(i + 1, remaining)
 
        take = 0
 
        if weights[i] <= remaining:
            take = (
                values[i]
                + solve(
                    i + 1,
                    remaining - weights[i]
                )
            )
 
        return max(take, skip)
 
    return solve(0, capacity)

python

Bottom-Up

def knapsack(weights, values, capacity):
 
    n = len(weights)
 
    dp = [
        [0] * (capacity + 1)
        for _ in range(n + 1)
    ]
 
    for i in range(1, n + 1):
 
        for w in range(capacity + 1):
 
            dp[i][w] = dp[i - 1][w]
 
            if weights[i - 1] <= w:
 
                dp[i][w] = max(
                    dp[i][w],
                    values[i - 1]
                    + dp[
                        i - 1
                    ][w - weights[i - 1]]
                )
 
    return dp[n][capacity]

python

Problem 6: Subset Sum

Question:

Can we select some numbers whose sum equals target?

Recursive

def subset_sum(nums, target):
 
    def solve(i, remaining):
 
        if remaining == 0:
            return True
 
        if i == len(nums):
            return False
 
        skip = solve(
            i + 1,
            remaining
        )
 
        take = False
 
        if nums[i] <= remaining:
            take = solve(
                i + 1,
                remaining - nums[i]
            )
 
        return take or skip
 
    return solve(0, target)

python

Memoized

from functools import lru_cache
 
def subset_sum(nums, target):
 
    @lru_cache(None)
    def solve(i, remaining):
 
        if remaining == 0:
            return True
 
        if i == len(nums):
            return False
 
        if nums[i] <= remaining:
            if solve(
                i + 1,
                remaining - nums[i]
            ):
                return True
 
        return solve(
            i + 1,
            remaining
        )
 
    return solve(0, target)

python

Bottom-Up

def subset_sum(nums, target):
 
    dp = [False] * (target + 1)
 
    dp[0] = True
 
    for num in nums:
 
        for s in range(
            target,
            num - 1,
            -1
        ):
            dp[s] = (
                dp[s]
                or dp[s - num]
            )
 
    return dp[target]

python

Important

For 0/1 Knapsack space optimization:

iterate backwards

because an item can only be used once.

Problem 7: Equal Sum Partition

If:

total sum = S

we need a subset with:

S / 2

So this becomes Subset Sum.

def canPartition(nums):
 
    total = sum(nums)
 
    if total % 2:
        return False
 
    return subset_sum(
        nums,
        total // 2
    )

python

Problem 8: Count Subsets With Sum K

Same state as Subset Sum.

But instead of asking:

Can it be done?

we ask:

How many ways?

Therefore:

OR → +

Recursive

def count_subsets(nums, target):
 
    def solve(i, remaining):
 
        if remaining == 0:
            return 1
 
        if i == len(nums):
            return 0
 
        answer = solve(
            i + 1,
            remaining
        )
 
        if nums[i] <= remaining:
            answer += solve(
                i + 1,
                remaining - nums[i]
            )
 
        return answer
 
    return solve(0, target)

python

Bottom-Up

def count_subsets(nums, target):
 
    dp = [0] * (target + 1)
 
    dp[0] = 1
 
    for num in nums:
 
        for s in range(
            target,
            num - 1,
            -1
        ):
            dp[s] += dp[s - num]
 
    return dp[target]

python

Problem 9: Minimum Subset Sum Difference

Find the reachable subset sum closest to:

total / 2

def min_subset_difference(nums):
 
    total = sum(nums)
 
    dp = [False] * (total + 1)
    dp[0] = True
 
    for num in nums:
 
        for s in range(
            total,
            num - 1,
            -1
        ):
            dp[s] |= dp[s - num]
 
    for s in range(
        total // 2,
        -1,
        -1
    ):
 
        if dp[s]:
            return total - 2 * s

python

Problem 10: Target Sum

Transform:

+ numbers
- numbers

into a subset-sum count problem.

def findTargetSumWays(nums, target):
 
    total = sum(nums)
 
    if abs(target) > total:
        return 0
 
    if (total + target) % 2:
        return 0
 
    subset = (total + target) // 2
 
    dp = [0] * (subset + 1)
 
    dp[0] = 1
 
    for num in nums:
 
        for s in range(
            subset,
            num - 1,
            -1
        ):
            dp[s] += dp[s - num]
 
    return dp[subset]

python

4. Pattern 3 — Unbounded Knapsack

The difference is simple:

0/1 Knapsack:
take → i + 1
 
Unbounded:
take → i

Because the item can be reused.

Common problems:

Coin Change
Coin Change II
Rod Cutting
Unbounded Knapsack

Problem 11: Coin Change

Find the minimum number of coins.

Recursive

def coinChange(coins, amount):
 
    def solve(remaining):
 
        if remaining == 0:
            return 0
 
        if remaining < 0:
            return float('inf')
 
        answer = float('inf')
 
        for coin in coins:
 
            answer = min(
                answer,
                1 + solve(
                    remaining - coin
                )
            )
 
        return answer
 
    answer = solve(amount)
 
    return (
        -1
        if answer == float('inf')
        else answer
    )

python

Memoized

from functools import lru_cache
 
def coinChange(coins, amount):
 
    @lru_cache(None)
    def solve(remaining):
 
        if remaining == 0:
            return 0
 
        if remaining < 0:
            return float('inf')
 
        answer = float('inf')
 
        for coin in coins:
 
            answer = min(
                answer,
                1 + solve(
                    remaining - coin
                )
            )
 
        return answer
 
    answer = solve(amount)
 
    return (
        -1
        if answer == float('inf')
        else answer
    )

python

Bottom-Up

def coinChange(coins, amount):
 
    dp = [float('inf')] * (amount + 1)
 
    dp[0] = 0
 
    for current in range(
        1,
        amount + 1
    ):
 
        for coin in coins:
 
            if coin <= current:
 
                dp[current] = min(
                    dp[current],
                    1 + dp[
                        current - coin
                    ]
                )
 
    return (
        -1
        if dp[amount] == float('inf')
        else dp[amount]
    )

python

Problem 12: Coin Change II

Count combinations instead of minimizing coins.

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

python

Notice the forward iteration:

coin → can be reused

Problem 13: Rod Cutting

Rod length is the capacity.

Piece length is the weight.

Price is the value.

def rod_cutting(prices, length):
 
    dp = [0] * (length + 1)
 
    for piece in range(
        1,
        length + 1
    ):
 
        for current in range(
            piece,
            length + 1
        ):
 
            dp[current] = max(
                dp[current],
                prices[piece - 1]
                + dp[current - piece]
            )
 
    return dp[length]

python

5. Pattern 4 — LCS / Two-Sequence DP

Recognition

If two sequences interact:

String A
String B

think:

dp[i][j]

Common problems:

LCS
Longest Common Substring
Edit Distance
Shortest Common Supersequence
Longest Palindromic Subsequence

Problem 14: Longest Common Subsequence

At positions i and j:

Characters match

1 + solve(i+1, j+1)

Characters don't match

max(
    solve(i+1,j),
    solve(i,j+1)
)

Recursive

def lcs(a, b):
 
    def solve(i, j):
 
        if (
            i == len(a)
            or j == len(b)
        ):
            return 0
 
        if a[i] == b[j]:
 
            return 1 + solve(
                i + 1,
                j + 1
            )
 
        return max(
            solve(i + 1, j),
            solve(i, j + 1)
        )
 
    return solve(0, 0)

python

Memoized

from functools import lru_cache
 
def lcs(a, b):
 
    @lru_cache(None)
    def solve(i, j):
 
        if (
            i == len(a)
            or j == len(b)
        ):
            return 0
 
        if a[i] == b[j]:
 
            return 1 + solve(
                i + 1,
                j + 1
            )
 
        return max(
            solve(i + 1, j),
            solve(i, j + 1)
        )
 
    return solve(0, 0)

python

Bottom-Up

def lcs(a, b):
 
    m = len(a)
    n = len(b)
 
    dp = [
        [0] * (n + 1)
        for _ in range(m + 1)
    ]
 
    for i in range(1, m + 1):
 
        for j in range(1, n + 1):
 
            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[m][n]

python

Problem 15: Longest Common Substring

Difference from LCS:

A mismatch resets the current substring.

def longest_common_substring(a, b):
 
    m = len(a)
    n = len(b)
 
    dp = [
        [0] * (n + 1)
        for _ in range(m + 1)
    ]
 
    answer = 0
 
    for i in range(1, m + 1):
 
        for j in range(1, n + 1):
 
            if a[i - 1] == b[j - 1]:
 
                dp[i][j] = (
                    1
                    + dp[i - 1][j - 1]
                )
 
                answer = max(
                    answer,
                    dp[i][j]
                )
 
    return answer

python

Problem 16: Longest Palindromic Subsequence

Use:

LPS(s) = LCS(s, reverse(s))

def longest_palindromic_subsequence(s):
 
    return lcs(
        s,
        s[::-1]
    )

python

Problem 17: Minimum Insertions to Make Palindrome

def min_insertions(s):
 
    return (
        len(s)
        - longest_palindromic_subsequence(s)
    )

python

Problem 18: Shortest Common Supersequence

Length:

len(A) + len(B) - LCS

def shortest_common_supersequence_length(a, b):
 
    return (
        len(a)
        + len(b)
        - lcs(a, b)
    )

python

Problem 19: Edit Distance

Operations:

Insert
Delete
Replace

Recursive

def edit_distance(a, b):
 
    def solve(i, j):
 
        if i == len(a):
            return len(b) - j
 
        if j == len(b):
            return len(a) - i
 
        if a[i] == b[j]:
            return solve(i + 1, j + 1)
 
        return 1 + min(
            solve(i + 1, j),       # delete
            solve(i, j + 1),       # insert
            solve(i + 1, j + 1)    # replace
        )
 
    return solve(0, 0)

python

Memoized

from functools import lru_cache
 
def edit_distance(a, b):
 
    @lru_cache(None)
    def solve(i, j):
 
        if i == len(a):
            return len(b) - j
 
        if j == len(b):
            return len(a) - i
 
        if a[i] == b[j]:
            return solve(i + 1, j + 1)
 
        return 1 + min(
            solve(i + 1, j),
            solve(i, j + 1),
            solve(i + 1, j + 1)
        )
 
    return solve(0, 0)

python

Bottom-Up

def edit_distance(a, b):
 
    m = len(a)
    n = len(b)
 
    dp = [
        [0] * (n + 1)
        for _ in range(m + 1)
    ]
 
    for i in range(m + 1):
        dp[i][0] = i
 
    for j in range(n + 1):
        dp[0][j] = j
 
    for i in range(1, m + 1):
 
        for j in range(1, n + 1):
 
            if a[i - 1] == b[j - 1]:
 
                dp[i][j] = dp[i - 1][j - 1]
 
            else:
 
                dp[i][j] = 1 + min(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                )
 
    return dp[m][n]

python

6. Pattern 5 — Grid DP

Recognition

Look for:

matrix/grid
move right/down
number of paths
minimum cost
maximum reward

State:

(row, column)

Problem 20: Unique Paths

Recursive

def uniquePaths(m, n):
 
    def solve(r, c):
 
        if r == m - 1 and c == n - 1:
            return 1
 
        if r >= m or c >= n:
            return 0
 
        return (
            solve(r + 1, c)
            + solve(r, c + 1)
        )
 
    return solve(0, 0)

python

Memoized

from functools import lru_cache
 
def uniquePaths(m, n):
 
    @lru_cache(None)
    def solve(r, c):
 
        if r == m - 1 and c == n - 1:
            return 1
 
        if r >= m or c >= n:
            return 0
 
        return (
            solve(r + 1, c)
            + solve(r, c + 1)
        )
 
    return solve(0, 0)

python

Bottom-Up

def uniquePaths(m, n):
 
    dp = [[1] * n for _ in range(m)]
 
    for r in range(1, m):
 
        for c in range(1, n):
 
            dp[r][c] = (
                dp[r - 1][c]
                + dp[r][c - 1]
            )
 
    return dp[m - 1][n - 1]

python

Problem 21: Unique Paths II

Blocked cells.

def uniquePathsWithObstacles(grid):
 
    m = len(grid)
    n = len(grid[0])
 
    dp = [[0] * n for _ in range(m)]
 
    if grid[0][0] == 1:
        return 0
 
    dp[0][0] = 1
 
    for r in range(m):
 
        for c in range(n):
 
            if grid[r][c] == 1:
                dp[r][c] = 0
                continue
 
            if r > 0:
                dp[r][c] += dp[r - 1][c]
 
            if c > 0:
                dp[r][c] += dp[r][c - 1]
 
    return dp[-1][-1]

python

Problem 22: Minimum Path Sum

Recursive

def minPathSum(grid):
 
    m = len(grid)
    n = len(grid[0])
 
    def solve(r, c):
 
        if r == m - 1 and c == n - 1:
            return grid[r][c]
 
        if r >= m or c >= n:
            return float('inf')
 
        return grid[r][c] + min(
            solve(r + 1, c),
            solve(r, c + 1)
        )
 
    return solve(0, 0)

python

Memoized

from functools import lru_cache
 
def minPathSum(grid):
 
    m = len(grid)
    n = len(grid[0])
 
    @lru_cache(None)
    def solve(r, c):
 
        if r == m - 1 and c == n - 1:
            return grid[r][c]
 
        if r >= m or c >= n:
            return float('inf')
 
        return grid[r][c] + min(
            solve(r + 1, c),
            solve(r, c + 1)
        )
 
    return solve(0, 0)

python

Bottom-Up

def minPathSum(grid):
 
    m = len(grid)
    n = len(grid[0])
 
    dp = [[0] * n for _ in range(m)]
 
    dp[0][0] = grid[0][0]
 
    for r in range(m):
 
        for c in range(n):
 
            if r == 0 and c == 0:
                continue
 
            top = (
                dp[r - 1][c]
                if r > 0
                else float('inf')
            )
 
            left = (
                dp[r][c - 1]
                if c > 0
                else float('inf')
            )
 
            dp[r][c] = (
                grid[r][c]
                + min(top, left)
            )
 
    return dp[-1][-1]

python

7. Pattern 6 — Longest Increasing Subsequence

Recognition

Look for:

Longest subsequence satisfying an ordering condition.

Typical state:

dp[i]
=
LIS ending at i

Problem 23: Longest Increasing Subsequence

A clean recursive formulation is:

def lengthOfLIS(nums):
 
    def solve(i, prev):
 
        if i == len(nums):
            return 0
 
        skip = solve(
            i + 1,
            prev
        )
 
        take = 0
 
        if (
            prev == -1
            or nums[i] > nums[prev]
        ):
            take = 1 + solve(
                i + 1,
                i
            )
 
        return max(
            take,
            skip
        )
 
    return solve(0, -1)

python

The state is:

i + previous index

Memoized:

from functools import lru_cache
 
def lengthOfLIS(nums):
 
    @lru_cache(None)
    def solve(i, prev):
 
        if i == len(nums):
            return 0
 
        skip = solve(
            i + 1,
            prev
        )
 
        take = 0
 
        if (
            prev == -1
            or nums[i] > nums[prev]
        ):
            take = 1 + solve(
                i + 1,
                i
            )
 
        return max(take, skip)
 
    return solve(0, -1)

python

For the standard bottom-up O(N²) DP:

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

python

8. Pattern 7 — State Machine DP

Recognition

Your state contains:

position/day
+
current status

Common examples:

Buy / Sell Stock
Cooldown
Transaction Fee
Limited Transactions

Problem 24: Best Time to Buy and Sell Stock II

State:

i
holding

Recursive

def maxProfit(prices):
 
    def solve(i, holding):
 
        if i == len(prices):
            return 0
 
        skip = solve(
            i + 1,
            holding
        )
 
        if holding:
 
            sell = (
                prices[i]
                + solve(i + 1, False)
            )
 
            return max(
                skip,
                sell
            )
 
        buy = (
            -prices[i]
            + solve(i + 1, True)
        )
 
        return max(
            skip,
            buy
        )
 
    return solve(0, False)

python

Memoized

from functools import lru_cache
 
def maxProfit(prices):
 
    @lru_cache(None)
    def solve(i, holding):
 
        if i == len(prices):
            return 0
 
        skip = solve(
            i + 1,
            holding
        )
 
        if holding:
 
            sell = (
                prices[i]
                + solve(i + 1, False)
            )
 
            return max(
                skip,
                sell
            )
 
        buy = (
            -prices[i]
            + solve(i + 1, True)
        )
 
        return max(
            skip,
            buy
        )
 
    return solve(0, False)

python

Bottom-Up

def maxProfit(prices):
 
    n = len(prices)
 
    dp = [[0] * 2 for _ in range(n + 1)]
 
    for i in range(n - 1, -1, -1):
 
        dp[i][0] = max(
            dp[i + 1][0],
            -prices[i] + dp[i + 1][1]
        )
 
        dp[i][1] = max(
            dp[i + 1][1],
            prices[i] + dp[i + 1][0]
        )
 
    return dp[0][0]

python

Problem 25: Stock With Cooldown

Now the state becomes:

holding
sold
cooldown

def maxProfit(prices):
 
    if not prices:
        return 0
 
    hold = -prices[0]
    sold = 0
    cooldown = 0
 
    for price in prices[1:]:
 
        old_hold = hold
        old_sold = sold
        old_cooldown = cooldown
 
        hold = max(
            old_hold,
            old_cooldown - price
        )
 
        sold = old_hold + price
 
        cooldown = max(
            old_cooldown,
            old_sold
        )
 
    return max(
        sold,
        cooldown
    )

python

The important lesson is not the code.

It's:

Add the extra condition to the DP state.

9. Pattern 8 — Interval / MCM DP

Recognition

Look for:

solve(i, j)

and:

try every split k

The structure is:

[i ---------------- j]
       ↓
   try every k
 
[i ---- k] [k+1 ---- j]

Common problems:

Matrix Chain Multiplication
Palindrome Partitioning
Burst Balloons
Boolean Parenthesization

Problem 26: Matrix Chain Multiplication

Recursive

def matrix_chain(arr):
 
    def solve(i, j):
 
        if i >= j:
            return 0
 
        answer = float('inf')
 
        for k in range(i, j):
 
            cost = (
                solve(i, k)
                + solve(k + 1, j)
                + arr[i - 1]
                * arr[k]
                * arr[j]
            )
 
            answer = min(
                answer,
                cost
            )
 
        return answer
 
    return solve(
        1,
        len(arr) - 1
    )

python

Memoized

from functools import lru_cache
 
def matrix_chain(arr):
 
    @lru_cache(None)
    def solve(i, j):
 
        if i >= j:
            return 0
 
        answer = float('inf')
 
        for k in range(i, j):
 
            cost = (
                solve(i, k)
                + solve(k + 1, j)
                + arr[i - 1]
                * arr[k]
                * arr[j]
            )
 
            answer = min(
                answer,
                cost
            )
 
        return answer
 
    return solve(
        1,
        len(arr) - 1
    )

python

Bottom-Up

Here the recursion depends on smaller intervals.

Therefore:

small interval
      ↓
larger interval

def matrix_chain(arr):
 
    n = len(arr)
 
    dp = [[0] * n for _ in range(n)]
 
    for length in range(2, n):
 
        for i in range(
            1,
            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]
                    + arr[i - 1]
                    * arr[k]
                    * arr[j]
                )
 
                dp[i][j] = min(
                    dp[i][j],
                    cost
                )
 
    return dp[1][n - 1]

python

Problem 27: Burst Balloons

The trick is to choose the last balloon to burst in an interval.

def maxCoins(nums):
 
    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
            ):
 
                coins = (
                    nums[left]
                    * nums[k]
                    * nums[right]
                    + dp[left][k]
                    + dp[k][right]
                )
 
                dp[left][right] = max(
                    dp[left][right],
                    coins
                )
 
    return dp[0][n - 1]

python

This is interval DP because:

left
right
split k

define the state.

10. Pattern 9 — Tree DP

Recognition

Look for:

Tree
+
answer depends on children

Typical flow:

Solve left
Solve right
    ↓
Combine
    ↓
Return information to parent

Problem 28: Diameter of Binary Tree

For every node:

left height
right height

Path through node:

left + right

Height returned:

1 + max(left, right)

def diameterOfBinaryTree(root):
 
    answer = 0
 
    def solve(node):
 
        nonlocal answer
 
        if not node:
            return 0
 
        left = solve(node.left)
        right = solve(node.right)
 
        answer = max(
            answer,
            left + right
        )
 
        return 1 + max(
            left,
            right
        )
 
    solve(root)
 
    return answer

python

This is naturally recursive, so forcing a separate DP array would make the solution worse.

Problem 29: Maximum Path Sum

def maxPathSum(root):
 
    answer = float('-inf')
 
    def solve(node):
 
        nonlocal answer
 
        if not node:
            return 0
 
        left = max(
            0,
            solve(node.left)
        )
 
        right = max(
            0,
            solve(node.right)
        )
 
        answer = max(
            answer,
            node.val + left + right
        )
 
        return node.val + max(
            left,
            right
        )
 
    solve(root)
 
    return answer

python

Problem 30: House Robber III

At every node:

Rob node
OR
Skip node

But if we rob the node, we cannot rob its children.

The state is naturally:

(node, robbed/skipped)

def rob(root):
 
    def solve(node):
 
        if not node:
            return (0, 0)
 
        left_rob, left_skip = solve(
            node.left
        )
 
        right_rob, right_skip = solve(
            node.right
        )
 
        rob_current = (
            node.val
            + left_skip
            + right_skip
        )
 
        skip_current = (
            max(left_rob, left_skip)
            + max(right_rob, right_skip)
        )
 
        return (
            rob_current,
            skip_current
        )
 
    return max(solve(root))

python

This is a good example where the recursive return value itself acts as the DP state.

11. Pattern 10 — DAG / Graph DP

Recognition

Look for:

Directed graph
+
No cycles
+
Answer depends on previous nodes

A DAG gives us a dependency order.

Typical problems:

Longest Path in DAG
Number of Paths
Minimum Cost Path

Problem 31: Longest Path in DAG

from collections import deque
 
def longest_path(n, edges):
 
    graph = [
        []
        for _ in range(n)
    ]
 
    indegree = [0] * n
 
    for u, v, weight in edges:
 
        graph[u].append(
            (v, weight)
        )
 
        indegree[v] += 1
 
    queue = deque(
        i
        for i in range(n)
        if indegree[i] == 0
    )
 
    dp = [0] * n
 
    while queue:
 
        u = queue.popleft()
 
        for v, weight in graph[u]:
 
            dp[v] = max(
                dp[v],
                dp[u] + weight
            )
 
            indegree[v] -= 1
 
            if indegree[v] == 0:
                queue.append(v)
 
    return max(dp)

python

Here the topological ordering replaces the recursion order.

12. Pattern 11 — Bitmask DP

Recognition

Think:

"I need to remember which elements have already been used."

For small N, represent the used elements with a bitmask.

Example:

10101
 
Element 0 → used
Element 1 → not used
Element 2 → used
Element 3 → not used
Element 4 → used

Typical state:

dp[mask][current]

Problem 32: Traveling Salesman

State:

mask
+
current city

def tsp(dist):
 
    n = len(dist)
 
    INF = float('inf')
 
    dp = [
        [INF] * n
        for _ in range(1 << n)
    ]
 
    dp[1][0] = 0
 
    for mask in range(1 << n):
 
        for city in range(n):
 
            if not (mask & (1 << city)):
                continue
 
            if dp[mask][city] == INF:
                continue
 
            for nxt in range(n):
 
                if mask & (1 << nxt):
                    continue
 
                new_mask = (
                    mask
                    | (1 << nxt)
                )
 
                dp[new_mask][nxt] = min(
                    dp[new_mask][nxt],
                    dp[mask][city]
                    + dist[city][nxt]
                )
 
    full = (1 << n) - 1
 
    return min(
        dp[full][city]
        + dist[city][0]
        for city in range(n)
    )

python

Complexity:

Time:  O(2^N × N²)
Space: O(2^N × N)

13. Pattern 12 — Digit DP

This is an advanced pattern.

Recognition

Usually:

Count numbers from 0 to N
+
Digit-related restriction

Typical state:

position
+
tight
+
additional state

For example:

dp(position, sum, tight)

Problem 33: Count Numbers With a Given Digit Sum

from functools import lru_cache
 
def count_digit_sum(N, target):
 
    digits = list(
        map(int, str(N))
    )
 
    @lru_cache(None)
    def solve(
        pos,
        current_sum,
        tight
    ):
 
        if current_sum > target:
            return 0
 
        if pos == len(digits):
            return int(
                current_sum == target
            )
 
        limit = (
            digits[pos]
            if tight
            else 9
        )
 
        answer = 0
 
        for digit in range(
            limit + 1
        ):
 
            answer += solve(
                pos + 1,
                current_sum + digit,
                tight
                and digit == limit
            )
 
        return answer
 
    return solve(
        0,
        0,
        True
    )

python

Digit DP is generally something to learn after the core patterns are comfortable.

14. Pattern 13 — Partition / String DP

Some problems don't fit neatly into LCS or MCM but involve breaking a string into valid pieces.

A common state is:

dp[i]
=
can we solve the prefix ending at i?

Problem 34: Word Break

Given a dictionary, determine whether the string can be segmented.

Example:

leetcode
 
"leet" + "code"

Recursive

def wordBreak(s, wordDict):
 
    words = set(wordDict)
 
    def solve(i):
 
        if i == len(s):
            return True
 
        for j in range(
            i + 1,
            len(s) + 1
        ):
 
            if (
                s[i:j] in words
                and solve(j)
            ):
                return True
 
        return False
 
    return solve(0)

python

Memoized

from functools import lru_cache
 
def wordBreak(s, wordDict):
 
    words = set(wordDict)
 
    @lru_cache(None)
    def solve(i):
 
        if i == len(s):
            return True
 
        for j in range(
            i + 1,
            len(s) + 1
        ):
 
            if (
                s[i:j] in words
                and solve(j)
            ):
                return True
 
        return False
 
    return solve(0)

python

Bottom-Up

def wordBreak(s, wordDict):
 
    words = set(wordDict)
 
    dp = [False] * (len(s) + 1)
 
    dp[0] = True
 
    for i in range(
        1,
        len(s) + 1
    ):
 
        for j in range(i):
 
            if (
                dp[j]
                and s[j:i] in words
            ):
                dp[i] = True
                break
 
    return dp[-1]

python

15. The Interview DP Problem Map

You don't need to memorize hundreds of DP problems.

Start with these.

1D DP

1. Climbing Stairs
2. Min Cost Climbing Stairs
3. House Robber
4. House Robber II
5. Decode Ways
6. Word Break

0/1 Knapsack

7. 0/1 Knapsack
8. Subset Sum
9. Equal Sum Partition
10. Count Subsets
11. Minimum Subset Sum Difference
12. Target Sum

Unbounded Knapsack

13. Coin Change
14. Coin Change II
15. Rod Cutting

LCS / String DP

16. Longest Common Subsequence
17. Longest Common Substring
18. Edit Distance
19. Shortest Common Supersequence
20. Longest Palindromic Subsequence
21. Minimum Insertions to Palindrome
22. Minimum Deletions to Palindrome

Grid DP

23. Unique Paths
24. Unique Paths II
25. Minimum Path Sum

LIS

26. Longest Increasing Subsequence
27. Maximum Length Chain
28. Russian Doll Envelopes

State Machine DP

29. Stock II
30. Stock With Cooldown
31. Stock With Transaction Fee
32. Stock With K Transactions

Interval DP

33. Matrix Chain Multiplication
34. Palindrome Partitioning
35. Burst Balloons
36. Boolean Parenthesization

Tree DP

37. Binary Tree Diameter
38. Maximum Path Sum
39. House Robber III
40. Binary Tree Cameras

Graph / DAG DP

41. Longest Path in DAG
42. Number of Paths in DAG
43. Minimum Cost Path in DAG

Bitmask DP

44. Traveling Salesman
45. Assignment Problem
46. Visit All Nodes

Digit DP

47. Count Numbers With Digit Sum
48. Count Numbers Without Repeated Digits
49. Count Numbers Matching Digit Constraints

16. The DP Recognition Cheat Sheet

When you see a new problem, don't immediately search for a formula.

Ask:

1. What are my choices?
 
2. What information defines the remaining problem?
 
3. Can I write solve(state)?
 
4. Does the same state appear repeatedly?
 
5. What does solve(state) return?

Then classify it.

                    DP
                     │
       ┌─────────────┼─────────────┐
       │             │             │
    Sequence      Choices       Structure
       │             │             │
       ↓             ↓             ↓
     1D DP      Take / Skip      Grid
       │             │           Tree
       │             ├── 0/1     DAG
       │             └── Unbounded
       │
       ├── LIS
       └── String
             │
             └── LCS

For more complex states:

Buy / Sell / Hold
    → State Machine DP
 
[i, j] + split k
    → Interval DP
 
Used elements
    → Bitmask DP
 
Digits + range
    → Digit DP

17. The Most Important Transformation

This is what you should practice repeatedly.

Start with:

def solve(i, state):

python

Understand the choices.

For example:

take = ...
skip = ...
return max(take, skip)

python

Then memoize:

@lru_cache(None)
def solve(i, state):

python

Then convert the state:

solve(i, state)
       ↓
dp[i][state]

Then look at the dependencies:

dp[i][state]
       ↓
dp[next_i][next_state]

Those dependencies determine:

table dimensions
iteration order
initialization
space optimization

18. The DP Learning Order

If you're preparing for interviews, learn these in this order.

Level 1 — Foundation

1. Climbing Stairs
2. House Robber
3. Decode Ways

Learn:

state
choices
recursion
memoization
1D DP

Level 2 — Knapsack

4. Subset Sum
5. Partition
6. Target Sum
7. Coin Change

Learn:

take / skip
0/1 vs unbounded
count vs boolean vs optimization

Level 3 — Two-Dimensional DP

8. LCS
9. Edit Distance
10. Unique Paths
11. Minimum Path Sum

Learn:

dp[i][j]

Level 4 — Advanced Structures

12. LIS
13. Stock DP
14. Interval DP
15. Tree DP

Level 5 — Advanced Interview / Hard

16. DAG DP
17. Bitmask DP
18. Digit DP

Final Mental Model

Don't memorize:

House Robber formula
Knapsack formula
LCS formula
Coin Change formula

Instead memorize the process:

                 NEW PROBLEM
                      │
                      ↓
                 Find choices
                      │
                      ↓
               Define recursive
                    state
                      │
                      ↓
                  Recursion
                      │
                      ↓
              Repeated states?
                 /          \
               No            Yes
               │              │
               │         Memoization
               │              │
               └──────┬───────┘
                      ↓
                 DP state
                      ↓
                Tabulation
                      ↓
             Can space be reduced?
                      │
                      ↓
               Optimized DP

The most important rule is:

Don't start with the DP array. Start with the recursive decision process.

Once you can write the correct recursion, memoization is usually just caching, and tabulation is usually just changing the order in which those same states are evaluated.

That is the core skill that makes DP problems predictable rather than mysterious.

Dynamic Programming Examples