Dynamic Programming Interview Mastery

Dynamic Programming is often taught as a collection of problems:

Climbing Stairs
House Robber
Knapsack
Coin Change
LCS
Edit Distance
Longest Increasing Subsequence
Matrix Chain Multiplication
Stock problems
Burst Balloons

The problem with learning DP this way is that every new problem feels like a completely new puzzle.

It isn't.

Most DP interview problems are variations of a relatively small number of state and transition patterns.

The goal of this guide is not to memorize solutions.

Formatting note: The examples, explanations, recurrences, and code walkthroughs below are intentionally preserved. The structure has been standardized around the same pattern: When to Use → Recognition → State → Transition → Working Example → Problems.

The goal is to learn how to look at a new problem and think:

What is my state, how can I calculate it, and what smaller states does it depend on?

Once you can answer those questions, the code becomes much easier.

Part I — DP Foundations

1. What Is Dynamic Programming?

At its core, DP is an optimized way of solving recursive problems.

Imagine:

                    solve(state)
                   /            \
              choice 1        choice 2
                 ↓                ↓
             subproblem       subproblem

Different branches may eventually reach the same state:

                 solve(A)
                /       \
             solve(B)  solve(C)
                \       /
                 solve(D)

Without DP, solve(D) may be calculated multiple times.

DP says:

If I have already solved a state, don't solve it again. Store its answer and reuse it.

This gives us the classic progression:

             RECURSION
                 ↓
       EXPLICIT MEMOIZATION
                 ↓
        BOTTOM-UP TABULATION
                 ↓
          SPACE OPTIMIZATION

But there is an important point:

Not every DP problem has take and skip.

Understanding this early will prevent a lot of confusion.

2. Not Every DP Problem Has Take/Skip

take/skip is a choice pattern, not a requirement for Dynamic Programming.

Some problems explicitly give you choices.

For example, in House Robber:

             house i
             /      \
          TAKE      SKIP
           ↓          ↓
        i + 2       i + 1

The recurrence is:

take = nums[i] + solve(i + 2)
skip = solve(i + 1)
 
return max(take, skip)

python

Here take and skip make sense because the problem gives us two decisions.

But some DP problems have no choice

Consider Counting Bits.

For a number:

6 = 110

we can remove the last binary bit:

110
 ↓
11

which gives:

6 // 2 = 3

The removed bit is:

6 % 2 = 0

Therefore:

bits(6) = bits(3) + 0

There was no choice.

We simply derived the current state from a smaller state.

The recurrence is:

dp[i] = dp[i // 2] + (i % 2)

python

So there are two broad ways you might arrive at a DP recurrence:

                            DP
                            │
          ┌──────────┴──────────┐
          ↓                                  ↓
    Choice-Based DP                  Dependency-Based DP
          │                                 │
     choices exist                   no decision needed
          │                                 │
      take / skip                    derive from states
      buy / sell                    dp[i-1], dp[i//2], etc.
      include / exclude

Choice-Based DP

Ask:

What choices do I have?

Examples:

0/1 Knapsack
House Robber
Subset Sum
Stock Trading
many game problems

Dependency-Based DP

Ask:

How can I derive this state from smaller states?

Examples:

Counting Bits
Fibonacci
Climbing Stairs
many linear/grid DP problems

The important rule is:

Don't force take/skip into a problem unless the problem actually contains a choice.

3. The Most Important DP Concept: State

Before writing code, ask:

What information completely describes the remaining problem?

That information becomes your state.

For example:

House Robber
 
solve(i)

because only the current index matters.

Knapsack:

solve(i, capacity)

because we need:

current item
remaining capacity

LCS:

solve(i, j)

because we need positions in both strings.

Stock:

solve(i, holding)

because we need:

current day
whether we own stock

TSP:

solve(mask, city)

because we need:

visited cities
current city

This gives us a powerful rule:

Your recursive parameters usually become your DP dimensions.

For example:

    solve(i)
       ↓
     dp[i]
 
 
   solve(i, j)
       ↓
    dp[i][j]
 
 
solve(i, capacity)
       ↓
 dp[i][capacity]
 
 
solve(mask, city)
       ↓
 dp[mask][city]

4. Why Use an Explicit Memo Array?

Python provides:

@lru_cache(None)

python

which is convenient.

But while learning DP, an explicit array/table is often much better.

Why?

Because it forces you to understand:

What does each DP cell actually mean?

For example:

memo[i]

python

means:

The answer for state i.

While:

memo[i][j]

python

means:

The answer for the state represented by (i, j).

This creates a direct connection:

Memoization	Tabulation
memo[i]	dp[i]
memo[i][j]	dp[i][j]
memo[i][capacity]	dp[i][capacity]
memo[mask][i]	dp[mask][i]

The memo table is therefore not some separate concept.

Your memo table is essentially the DP table, except that recursion decides which cells get calculated and when.

5. The Universal DP Workflow

For an unfamiliar DP problem, use this process.

Problem
   ↓
Understand the state
   ↓
Ask: Are there choices?
   ↓
If yes → identify choices
If no  → find dependency
   ↓
Write recursion
   ↓
Add explicit memo table
   ↓
Understand what each cell means
   ↓
Convert to bottom-up DP
   ↓
Determine iteration order
   ↓
Optimize space if possible

Let's now apply this to the major interview patterns.

Part II — DP Pattern Catalog

Pattern 1: 1D / Linear DP

The state depends primarily on one index:

dp[i]

But remember:

1D DP does not necessarily mean take/skip.

House Robber is choice-based.

Counting Bits is dependency-based.

They can both be 1D DP.

Example 1: House Robber

You have:

[2, 7, 9, 3, 1]

You cannot rob adjacent houses.

This is a choice-based DP problem.

Step 1: Define the state

solve(i)

python

means:

Maximum money we can obtain starting from house i.

Step 2: Identify choices

At house i:

             house i
             /      \
          TAKE      SKIP
           ↓          ↓
        i + 2       i + 1

Step 3: Recursion

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

Step 4: Explicit Memoization

There are n states:

0, 1, 2, ..., n-1

Therefore:

memo = [-1] * n

python

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

python

Now:

memo[i]

means:

Maximum money obtainable starting from house i.

Step 5: Convert to Bottom-Up

Our recurrence is:

dp[i] = max(
    nums[i] + dp[i+2],
    dp[i+1]
)

dp[i] depends on future states:

dp[i+1]
dp[i+2]

Therefore we calculate:

n → 0

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

Step 6: Space Optimization

Only two future states are needed:

dp[i+1]
dp[i+2]

So:

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

python

Example 2: Counting Bits

This is still 1D DP, but there is no take/skip.

Given:

n = 6

return:

[0,1,1,2,1,2,2]

Step 1: Define the state

dp[i]

means:

Number of 1 bits in the binary representation of i.

Step 2: Find the dependency

For:

6 = 110

removing the last bit gives:

11 = 3

So:

6 // 2 = 3

The removed bit is:

6 % 2 = 0

Therefore:

dp[6] = dp[3] + 0

In general:

dp[i] = dp[i // 2] + (i % 2)

There is no take or skip.

We're simply deriving the current state from a smaller state.

Step 3: Recursion

def solve(i):
 
    if i == 0:
        return 0
 
    return solve(i // 2) + (i % 2)

python

Step 4: Explicit Memoization

def countBits(n):
 
    memo = [-1] * (n + 1)
 
    memo[0] = 0
 
    def solve(i):
 
        if memo[i] != -1:
            return memo[i]
 
        memo[i] = solve(i // 2) + (i % 2)
 
        return memo[i]
 
    for i in range(n + 1):
        solve(i)
 
    return memo

python

The table becomes:

index:  0  1  2  3  4  5  6
memo:   0  1  1  2  1  2  2

Step 5: Bottom-Up

The recurrence:

dp[i] = dp[i // 2] + (i % 2)

depends on:

i // 2 < i

Therefore we process:

0 → n

def countBits(n):
 
    dp = [0] * (n + 1)
 
    for i in range(1, n + 1):
 
        dp[i] = dp[i // 2] + (i % 2)
 
    return dp

python

Notice the contrast:

House Robber
 
dp[i]
 ↓
dp[i+1], dp[i+2]
 
→ iterate right to left

while:

Counting Bits
 
dp[i]
 ↓
dp[i//2]
 
→ iterate left to right

Both are 1D DP.

But one is choice-based, while the other is dependency-based.

Problems

Additional Problems

Pattern 2: 0/1 Knapsack

When to Use

Think 0/1 Knapsack when the problem involves choosing from a collection of items where each item can be used at most once, usually with a target, capacity, sum, or budget constraint.

Recognition Signals

Choose / Don't Choose
+
Each item used at most once
+
Target / Capacity / Sum

Think:

0/1 Knapsack

This is one of the most important choice-based DP patterns.

The core structure:

             ITEM
            /    \
         TAKE    SKIP

Each item can be used at most once.

Example: 0/1 Knapsack

weights = [1,3,4,5]
values  = [1,4,5,7]
capacity = 7

State

solve(i, remaining)

means:

Maximum value using items from i onward with remaining capacity.

Recursion

def knapsack(weights, values, capacity):
 
    n = len(weights)
 
    def solve(i, remaining):
 
        if i == n 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

Memoization

State:

(i, remaining)

Therefore:

memo[i][remaining]

def knapsack(weights, values, capacity):
 
    n = len(weights)
 
    memo = [
        [-1] * (capacity + 1)
        for _ in range(n)
    ]
 
    def solve(i, remaining):
 
        if i == n or remaining == 0:
            return 0
 
        if memo[i][remaining] != -1:
            return memo[i][remaining]
 
        skip = solve(i + 1, remaining)
 
        take = 0
 
        if weights[i] <= remaining:
 
            take = values[i] + solve(
                i + 1,
                remaining - weights[i]
            )
 
        memo[i][remaining] = max(
            take,
            skip
        )
 
        return memo[i][remaining]
 
    return solve(0, capacity)

python

The table represents:

memo[i][remaining]
=
best value using items from i onward
with this much capacity remaining

Bottom-Up

Because:

dp[i][capacity]

depends on:

dp[i+1][...]

we can process items backwards.

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

python

Space Optimization

Since each row only depends on the next row, we can reduce:

O(N × W)

to:

O(W)

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

python

The backward iteration is important because each item can only be used once.

Problems

0/1 Knapsack Family

Once you recognize:

Take / Don't Take
+
Each item used at most once
+
Target / Capacity

think:

0/1 Knapsack

Then change the operation depending on the question.

Maximum value
    → max()
 
Can we make target?
    → OR
 
How many ways?
    → +
 
Minimum something
    → min()

Additional Problems

Pattern 3: Unbounded Knapsack

When to Use

Think Unbounded Knapsack when items can be selected multiple times and the problem involves a target, capacity, amount, or optimization objective.

Recognition Signals

Choose / Don't Choose
+
Items can be reused
+
Target / Capacity / Amount

Think:

Unbounded Knapsack

The same choice structure exists:

TAKE / SKIP

but the item can be reused.

The critical difference is:

0/1:
 
take → solve(i + 1, ...)
 
 
Unbounded:
 
take → solve(i, ...)

Example: Coin Change

Coins:

[1,2,5]

Amount:

Goal:

Minimum number of coins.

Recursion

def coinChange(coins, amount):
 
    n = len(coins)
 
    def solve(i, remaining):
 
        if remaining == 0:
            return 0
 
        if i == n:
            return float("inf")
 
        skip = solve(i + 1, remaining)
 
        take = float("inf")
 
        if coins[i] <= remaining:
 
            take = 1 + solve(
                i,
                remaining - coins[i]
            )
 
        return min(take, skip)
 
    answer = solve(0, amount)
 
    return -1 if answer == float("inf") else answer

python

Memoization

def coinChange(coins, amount):
 
    n = len(coins)
 
    memo = [
        [-1] * (amount + 1)
        for _ in range(n)
    ]
 
    def solve(i, remaining):
 
        if remaining == 0:
            return 0
 
        if i == n:
            return float("inf")
 
        if memo[i][remaining] != -1:
            return memo[i][remaining]
 
        skip = solve(i + 1, remaining)
 
        take = float("inf")
 
        if coins[i] <= remaining:
 
            take = 1 + solve(
                i,
                remaining - coins[i]
            )
 
        memo[i][remaining] = min(
            take,
            skip
        )
 
        return memo[i][remaining]
 
    answer = solve(0, amount)
 
    return -1 if answer == float("inf") else answer

python

Notice:

solve(i, remaining - coins[i])

python

We don't increment i.

That's the defining characteristic of unbounded choice.

Bottom-Up

A common 2D formulation is:

def coinChange(coins, amount):
 
    n = len(coins)
 
    dp = [
        [float("inf")] * (amount + 1)
        for _ in range(n + 1)
    ]
 
    # remaining == 0
    for i in range(n + 1):
        dp[i][0] = 0
 
    for i in range(n - 1, -1, -1):
 
        for remaining in range(1, amount + 1):
 
            # skip
            skip = dp[i + 1][remaining]
 
            # take
            take = float("inf")
 
            if coins[i] <= remaining:
                take = 1 + dp[i][remaining - coins[i]]
 
            dp[i][remaining] = min(
                take,
                skip
            )
 
    answer = dp[0][amount]
 
    return -1 if answer == float("inf") else answer

python

A common 1D formulation is:

dp[amount]
=
minimum coins needed for amount

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

Problems

Additional Problems

Pattern 4: Two-Sequence DP

When to Use

Think Two-Sequence DP when a problem involves two strings or sequences and the answer depends on positions in both.

The common state is:

solve(i, j)

where:

i = position in the first sequence
j = position in the second sequence

Two-Sequence DP is an umbrella pattern:

Two-Sequence DP
│
├── Sequence Comparison
│   └── LCS / Edit Distance / SCS / etc.
│
├── Two-Source Consumption
│   └── Interleaving
│
└── Pattern Matching
    └── Wildcard / Regex

Recognition Signals

Two strings / sequences
        +
Answer depends on positions in both
        +
solve(i, j)

Then ask:

What relationship exists between the two sequences?

Compare two sequences
        → Sequence Comparison
 
Consume from two sources
        → Two-Source Consumption
 
Match input against a pattern
        → Pattern Matching

Sub-Pattern 1: Sequence Comparison

Use this when two sequences are compared while preserving their relative order.

Typical problems:

Example: LCS

A = "abcde"
B = "ace"

State:

solve(i, j)

means:

LCS of A[i:] and B[j:].

If characters match:

A[i] == B[j]
 
1 + solve(i + 1, j + 1)

Otherwise, skip one:

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

Recursion

def lcs(a, b):
 
    m = len(a)
    n = len(b)
 
    def solve(i, j):
 
        if i == m or j == n:
            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

Memoization

def lcs(a, b):
 
    m = len(a)
    n = len(b)
 
    memo = [[-1] * n for _ in range(m)]
 
    def solve(i, j):
 
        if i == m or j == n:
            return 0
 
        if memo[i][j] != -1:
            return memo[i][j]
 
        if a[i] == b[j]:
            memo[i][j] = 1 + solve(i + 1, j + 1)
        else:
            memo[i][j] = max(
                solve(i + 1, j),
                solve(i, j + 1)
            )
 
        return memo[i][j]
 
    return solve(0, 0)

python

Bottom-Up

The recurrence uses:

dp[i + 1][j]
dp[i][j + 1]
dp[i + 1][j + 1]

so fill:

bottom-right → top-left

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

python

The key decision is:

Match
    → use both characters
    → move diagonally
 
No match
    → skip A
    OR
    → skip B

LCS Reconstruction

The DP table gives us the LCS length, but sometimes we need the actual subsequence.

Start at:

(i, j) = (0, 0)

If the characters match, add the character and move diagonally:

a[i] == b[j]
 
answer.append(a[i])
i += 1
j += 1

Otherwise, follow the state with the larger LCS value:

dp[i + 1][j] >= dp[i][j + 1]
    → skip A[i]
 
otherwise
    → skip B[j]

Bottom-Up Reconstruction

def lcs_string(a, b):
 
    m = len(a)
    n = len(b)
 
    dp = [[0] * (n + 1) for _ in range(m + 1)]
 
    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
 
            if a[i] == b[j]:
                dp[i][j] = 1 + dp[i + 1][j + 1]
            else:
                dp[i][j] = max(
                    dp[i + 1][j],
                    dp[i][j + 1]
                )
 
    i = 0
    j = 0
    answer = []
 
    while i < m and j < n:
 
        if a[i] == b[j]:
 
            answer.append(a[i])
            i += 1
            j += 1
 
        elif dp[i + 1][j] >= dp[i][j + 1]:
 
            i += 1
 
        else:
 
            j += 1
 
    return "".join(answer)

python

The reconstruction rule is:

Match
    → add character
    → move diagonally
 
Skip A
    → move i
 
Skip B
    → move j

Reconstruction follows the decisions that produced the optimal DP value.

Sub-Pattern 2: Two-Source Consumption

Use this when two sequences are consumed to construct or match a third sequence.

The canonical example:

Interleaving String

State:

solve(i, j)

where i and j represent how many characters have been consumed from s1 and s2.

The position in s3 is derived:

k = i + j

At every step:

Take from s1
    → solve(i + 1, j)
 
OR
 
Take from s2
    → solve(i, j + 1)

Recurrence

def solve(i, j):
 
    k = i + j
 
    if i == len(s1) and j == len(s2):
        return True
 
    if i < len(s1) and s1[i] == s3[k]:
        if solve(i + 1, j):
            return True
 
    if j < len(s2) and s2[j] == s3[k]:
        if solve(i, j + 1):
            return True
 
    return False

python

With memoization:

memo[i][j]

and bottom-up, the dependencies are:

dp[i + 1][j]
dp[i][j + 1]

so fill:

bottom-right → top-left

The key decision is:

LCS:
skip A OR skip B
 
Interleaving:
consume from A OR consume from B

Sub-Pattern 3: Pattern Matching

Use this when one sequence is a pattern that controls how another sequence is matched.

Typical problems:

State:

solve(i, j)

where:

i = current position in input
j = current position in pattern

For Wildcard Matching:

? → matches exactly one character
 
* → matches zero or more characters

Normal character / ?:

solve(i + 1, j + 1)

For *:

solve(i, j + 1)   # * matches nothing
 
OR
 
solve(i + 1, j)   # * consumes one character

Recurrence

def solve(i, j):
 
    if i == m:
        return all(c == '*' for c in p[j:])
 
    if j == n:
        return False
 
    if p[j] == '*':
        return (
            solve(i, j + 1)
            or solve(i + 1, j)
        )
 
    if p[j] == '?' or p[j] == s[i]:
        return solve(i + 1, j + 1)
 
    return False

python

Memoization stores:

memo[i][j]

and bottom-up uses:

dp[i][j + 1]
dp[i + 1][j]
dp[i + 1][j + 1]

so again:

bottom-right → top-left

Comparing the Sub-Patterns

The state may look identical:

dp[i][j]

but the meaning of the transition is different.

Pattern	Decision
Sequence Comparison	Match or skip one sequence
Interleaving	Consume from sequence 1 or 2
Pattern Matching	Follow the pattern's rules

For example:

LCS
 
match
    → move diagonally
 
no match
    → skip A OR skip B

Interleaving
 
s1[i] matches
    → consume s1
 
s2[j] matches
    → consume s2

Wildcard
 
'*'
    → match nothing
    OR
    → consume a character

State tells you the dimensions. Transition tells you the pattern.

Common Mistake

Don't assume every:

dp[i][j]

problem is LCS.

Always ask:

What does i represent?
What does j represent?
What are my choices?

Also remember:

Subsequence
→ characters can be skipped
 
Substring
→ characters must be contiguous

Problem Set

Sequence Comparison

Two-Source Consumption

Pattern Matching

Pattern 5: Grid DP

When to Use

Think Grid DP when the input is a matrix and movement between cells is restricted.

Recognition Signals

Grid
+
Restricted movement
+
Count / Minimum / Maximum

Grid DP appears when you move through a matrix.

Typical problems:

Example: Unique Paths

A robot starts at:

(0,0)

and wants to reach:

(m-1,n-1)

It can move:

→
↓

State

solve(r, c)

means:

Number of ways to reach the destination from (r,c).

Recursion

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

No take/skip here in the traditional sense.

We have movement choices:

DOWN
RIGHT

The same choice principle applies, but the names take/skip would be misleading.

Memoization

def uniquePaths(m, n):
 
    memo = [
        [-1] * n
        for _ in range(m)
    ]
 
    def solve(r, c):
 
        if r == m - 1 and c == n - 1:
            return 1
 
        if r >= m or c >= n:
            return 0
 
        if memo[r][c] != -1:
            return memo[r][c]
 
        memo[r][c] = (
            solve(r + 1, c)
            + solve(r, c + 1)
        )
 
        return memo[r][c]
 
    return solve(0, 0)

python

Bottom-Up

Because:

dp[r][c]
depends on
dp[r+1][c]
dp[r][c+1]

we calculate:

bottom-right → top-left

def uniquePaths(m, n):
 
    dp = [
        [0] * n
        for _ in range(m)
    ]
 
    dp[m - 1][n - 1] = 1
 
    for r in range(m - 1, -1, -1):
 
        for c in range(n - 1, -1, -1):
 
            if r == m - 1 and c == n - 1:
                continue
 
            down = (
                dp[r + 1][c]
                if r + 1 < m
                else 0
            )
 
            right = (
                dp[r][c + 1]
                if c + 1 < n
                else 0
            )
 
            dp[r][c] = down + right
 
    return dp[0][0]

python

Problems

Pattern 6: Longest Increasing Subsequence

When to Use

Think LIS-style DP when you select a subsequence whose elements must satisfy an ordering or compatibility condition.

Recognition Signals

One sequence
+
Choose a subsequence
+
Selected elements must satisfy an ordering condition

LIS asks for the longest subsequence satisfying an ordering condition.

Examples:

Example

[10,9,2,5,3,7,101,18]

One answer:

2 → 3 → 7 → 101

State

A recursive state can be:

solve(i, previous)

meaning:

Best increasing subsequence starting from i, given the previously selected element.

Choices

SKIP nums[i]
 
OR
 
TAKE nums[i]
if nums[i] > previous

Recursion

def lis(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

Memoization

Because prev can be -1, we shift it by one position.

def lis(nums):
 
    n = len(nums)
 
    memo = [
        [-1] * (n + 1)
        for _ in range(n)
    ]
 
    def solve(i, prev):
 
        if i == n:
            return 0
 
        key = prev + 1
 
        if memo[i][key] != -1:
            return memo[i][key]
 
        skip = solve(i + 1, prev)
 
        take = 0
 
        if prev == -1 or nums[i] > nums[prev]:
 
            take = 1 + solve(
                i + 1,
                i
            )
 
        memo[i][key] = max(
            take,
            skip
        )
 
        return memo[i][key]
 
    return solve(0, -1)

python

Bottom-Up

def lis(nums):
    n = len(nums)
 
    dp = [[0] * (n + 1) for _ in range(n + 1)]
 
    for i in range(n - 1, -1, -1):
        for prev in range(-1, i):
 
            # Skip nums[i]
            skip = dp[i + 1][prev + 1]
 
            # Take nums[i]
            take = 0
 
            if prev == -1 or nums[i] > nums[prev]:
                take = 1 + dp[i + 1][i + 1]
 
            dp[i][prev + 1] = max(take, skip)
 
    return dp[0][0]

python

A useful alternative state is:

dp[i]
=
LIS ending at i

Then:

def lis(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)

python

This is an important lesson:

A problem can have multiple valid DP state definitions.

You don't need to memorize one exact table.

You need to define a state that contains enough information to calculate the answer.

Problems

Pattern 7: State Machine DP

When to Use

Think State Machine DP when the answer depends on both your current position and a small number of modes or conditions.

Recognition Signals

Position
+
Current state / mode
+
State transitions

This pattern is especially common in stock problems.

The state includes:

position
+
current condition

For example:

(day, holding)

Example: Stock Trading

At each day:

NOT HOLDING
    ├── BUY
    └── SKIP
 
HOLDING
    ├── SELL
    └── HOLD

This is a choice-based state machine.

Recursion

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,
                0
            )
 
            return max(skip, sell)
 
        buy = -prices[i] + solve(
            i + 1,
            1
        )
 
        return max(skip, buy)
 
    return solve(0, 0)

python

Memoization

def maxProfit(prices):
 
    n = len(prices)
 
    memo = [
        [-1] * 2
        for _ in range(n)
    ]
 
    def solve(i, holding):
 
        if i == n:
            return 0
 
        if memo[i][holding] != -1:
            return memo[i][holding]
 
        skip = solve(
            i + 1,
            holding
        )
 
        if holding:
 
            sell = prices[i] + solve(
                i + 1,
                0
            )
 
            memo[i][holding] = max(
                skip,
                sell
            )
 
        else:
 
            buy = -prices[i] + solve(
                i + 1,
                1
            )
 
            memo[i][holding] = max(
                skip,
                buy
            )
 
        return memo[i][holding]
 
    return solve(0, 0)

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):
 
        for holding in range(2):
 
            skip = dp[i + 1][holding]
 
            if holding:
 
                sell = prices[i] + dp[i + 1][0]
 
                dp[i][holding] = max(skip, sell)
 
            else:
 
                buy = -prices[i] + dp[i + 1][1]
 
                dp[i][holding] = max(skip, buy)
 
    return dp[0][0]

python

Problems

Pattern 8: Interval DP / Matrix Chain Multiplication

When to Use

Think Interval DP when the state represents a range [i, j] and you try possible split points inside that range.

Recognition Signals

Range [i, j]
+
Choose split k

Think:

Interval DP

Use this pattern when the state is an interval:

[i ... j]

and you try possible split points:

[i ... k] [k+1 ... j]

Typical problems:

Matrix Chain Multiplication
Burst Balloons
Palindrome Partitioning
Boolean Parenthesization
Optimal BST

Recognition Pattern

If you see:

solve(i, j)
 
for k in range(i, j):
    solve(i, k)
    solve(k + 1, j)

python

think:

Interval DP

Matrix Chain Multiplication

Different parenthesizations have different costs:

(A × B) × C
 
vs
 
A × (B × C)

Recursion

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

python

Memoization

def matrixChain(arr):
 
    n = len(arr)
 
    memo = [
        [-1] * n
        for _ in range(n)
    ]
 
    def solve(i, j):
 
        if i >= j:
            return 0
 
        if memo[i][j] != -1:
            return memo[i][j]
 
        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
            )
 
        memo[i][j] = answer
 
        return answer
 
    return solve(1, n - 1)

python

Bottom-Up

An interval depends on smaller intervals.

Therefore calculate:

short intervals
      ↓
longer intervals

def matrixChain(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

Problems

Pattern 9: Tree DP

When to Use

Think Tree DP when a node's answer depends on independently computed information from its children.

Recognition Signals

Tree
+
Subtree results
+
Child → Parent dependency

Tree DP works differently because the information naturally flows from children to parents.

             node
            /    \
         left    right
           ↓       ↓
        result   result
            \     /
             node

Typical problems:

Diameter of Binary Tree
Maximum Path Sum
House Robber III
Binary Tree Cameras

Example: Diameter

At each node:

left height
right height

Path through node:

left + right

Value returned upward:

1 + max(left, right)

Recursion

def diameter(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

Tree DP often naturally visits each node once, so the recursive solution may already be O(N).

For more complex tree problems, however, the state may become:

memo[node][state]

Problems

Pattern 10: DAG / Graph DP

When to Use

Think DAG DP when a directed acyclic graph provides a dependency structure and the answer at one node can be derived from other nodes.

Recognition Signals

Directed
+
Acyclic
+
Optimization / Counting over dependencies

A Directed Acyclic Graph provides a natural dependency order.

Example:

A → B → D
 \       ↑
  → C ───┘

If:

u → v

then the answer for v can depend on the answer for u.

Longest Path in DAG

A typical transition:

dp[v] = max(
    dp[v],
    dp[u] + weight
)

Recursive + Memoization

memo = [-1] * n
 
def solve(node):
 
    if memo[node] != -1:
        return memo[node]
 
    answer = 0
 
    for neighbor, weight in graph[node]:
 
        answer = max(
            answer,
            weight + solve(neighbor)
        )
 
    memo[node] = answer
 
    return answer

python

Bottom-Up

Use topological order:

for u in topo_order:
 
    for v, weight in graph[u]:
 
        dp[v] = max(
            dp[v],
            dp[u] + weight
        )

python

The important recognition:

DAG + optimization/counting over dependencies often means Graph DP.

Problems

Pattern 11: Bitmask DP

When to Use

Think Bitmask DP when the state needs to remember exactly which elements from a small set have already been used.

Recognition Signals

Small N
+
Subset / visited set matters
+
Need exact membership information

Bitmask DP is useful when the state needs to remember:

Which elements have already been used?

For:

A B C D

we can represent selected elements using bits:

meaning:

A → used
B → unused
C → used
D → unused

A common state is:

dp[mask][i]

meaning:

We have visited the elements in mask and are currently at i.

Example: Traveling Salesman

At each city:

Go to an unvisited city

Recursion

def solve(mask, city):
 
    if mask == all_visited:
        return cost[city][0]
 
    answer = float("inf")
 
    for nxt in range(n):
 
        if not (mask & (1 << nxt)):
 
            answer = min(
                answer,
                cost[city][nxt]
                + solve(
                    mask | (1 << nxt),
                    nxt
                )
            )
 
    return answer

python

Memoization

memo = [
    [-1] * n
    for _ in range(1 << n)
]

python

Then:

def solve(mask, city):
 
    if mask == all_visited:
        return cost[city][0]
 
    if memo[mask][city] != -1:
        return memo[mask][city]
 
    answer = float("inf")
 
    for nxt in range(n):
 
        if not (mask & (1 << nxt)):
 
            answer = min(
                answer,
                cost[city][nxt]
                + solve(
                    mask | (1 << nxt),
                    nxt
                )
            )
 
    memo[mask][city] = answer
 
    return answer

python

The number of states is roughly:

2^N × N

so this pattern is generally used for relatively small N.

Problems

Pattern 12: Digit DP

When to Use

Think Digit DP when you need to count or optimize over numbers in a range while enforcing conditions on their digits.

Recognition Signals

Number range
+
Digit constraints
+
Count / optimize

Digit DP is an advanced pattern.

Use it when the problem asks you to count numbers satisfying a property based on their digits.

Examples:

Digit sum constraints
Numbers without repeated digits
Numbers containing a particular digit
Counting numbers between two bounds

A typical state:

dp[position][tight][other_state]

The `tight` Concept

Suppose the upper bound is:

If we choose:

as the first digit, we're already smaller than the bound:

4 < 5

So subsequent digits can range freely.

But if we choose:

we are still equal to the bound prefix.

Then the next digit cannot exceed:

That's what tight represents.

tight = True
    ↓
must respect upper bound
 
tight = False
    ↓
free to choose remaining digits

Problems

Part III — DP Direction and Tabulation

1. Choosing DP Direction

This is one of the most important ideas when converting recursion to tabulation.

Don't memorize:

"DP always goes from 0 to n."

It doesn't.

Look at the recurrence.

If the state depends on smaller indices

Example:

dp[i] = dp[i-1] + dp[i-2]

Then:

0 → n

Example:

Counting Bits
 
dp[i] = dp[i//2] + i%2

because:

i//2 < i

So:

0 → n

If the state depends on future indices

Example:

dp[i] = max(
    nums[i] + dp[i+2],
    dp[i+1]
)

Then:

n → 0

If the state is an interval

Example:

dp[i][j]

depends on smaller intervals.

Then:

short intervals → long intervals

The Real Rule

Don't ask:

Should I start at 0 or n?

Ask:

What states does my current state depend on?

Then calculate those dependencies first.

dp[i] depends on dp[i-1]
        ↓
calculate i-1 first
        ↓
left → right
 
 
dp[i] depends on dp[i+1]
        ↓
calculate i+1 first
        ↓
right → left

Therefore:

DP direction is a consequence of the dependency graph.

2. The Complete DP Pattern Map

                         DP
                          │
          ┌───────────────┼────────────────┐
          │               │                │
       1D State        Multiple State    Structure
          │               │                │
          ↓               ↓                ↓
       1D DP           Knapsack          Tree DP
       LIS             LCS               DAG DP
       Grid            Stock
                       Interval
                       Bitmask
                       Digit

A more practical recognition guide:

One index
    → 1D DP
 
Take / Don't Take
    → 0/1 Knapsack
 
Reusable items
    → Unbounded Knapsack
 
Two sequences
    → LCS
 
Matrix movement
    → Grid DP
 
Increasing subsequence
    → LIS
 
Buy / Sell / Hold
    → State Machine DP
 
Range [i,j] + split
    → Interval DP
 
Children → Parent
    → Tree DP
 
DAG dependencies
    → Graph DP
 
Track used elements
    → Bitmask DP
 
Digit constraints
    → Digit DP

3. Maximum, Minimum, Count, or Boolean?

After identifying the state and transitions, determine what the problem wants.

Maximum

Keywords:

maximum
largest
longest
best
maximum profit

Usually:

max(...)

python

Minimum

Keywords:

minimum
smallest
fewest
least
minimum cost

Usually:

min(...)

python

Count

Keywords:

how many
number of ways
count

Usually:

choice1 + choice2

python

Boolean

Keywords:

possible?
can we?
is there a way?

Usually:

choice1 or choice2

python

This is why problems such as:

Subset Sum
Count Subsets
Knapsack

can share the same underlying structure while having completely different-looking code.

4. The Universal Recursive DP Template

Do not memorize take/skip as the universal template.

Instead, start with:

def solve(state):
 
    # Base case
    if base_case:
        return base_answer
 
    # Already solved?
    if memo[state] != UNVISITED:
        return memo[state]
 
    # Calculate from choices or dependencies
    answer = ...
 
    # Store
    memo[state] = answer
 
    return answer

python

Then determine what goes inside answer.

For a choice problem:

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

python

For a dependency problem:

answer = smaller_state + something

python

For a movement problem:

answer = down + right

python

For an interval problem:

answer = best over all k

python

The state and transition are the important parts.

5. The Interview DP Checklist

When you encounter a new problem, ask these questions in order:

1. What is the problem asking for?
 
   Maximum?
   Minimum?
   Count?
   Existence?
 
                    ↓
 
2. What information defines my state?
 
                    ↓
 
3. Does the problem give me choices?
 
   YES
      ↓
   Identify choices
   (take/skip, buy/sell, etc.)
 
   NO
      ↓
   Find how the state
   depends on smaller states
 
                    ↓
 
4. Write the recursive solution.
 
                    ↓
 
5. Identify repeated states.
 
                    ↓
 
6. Create an explicit memo array/table.
 
                    ↓
 
7. Ask:
   "What does memo[state] mean?"
 
                    ↓
 
8. Look at the recurrence.
 
   What states does it depend on?
 
                    ↓
 
9. Determine iteration order.
 
                    ↓
 
10. Convert to bottom-up DP.
 
                    ↓
 
11. Can space be optimized?

6. DP Pattern Cheat Sheet

Structure	Pattern	Typical State
Sequence + previous states	1D DP	`dp[i]`
Take / Don't Take	0/1 Knapsack	`dp[i][capacity]`
Reusable items	Unbounded Knapsack	`dp[i][capacity]`
Two sequences	LCS	`dp[i][j]`
Grid movement	Grid DP	`dp[r][c]`
Increasing subsequence	LIS	`dp[i]`
Buy / Sell / Hold	State Machine	`dp[i][state]`
Range `[i,j]` + split	Interval DP	`dp[i][j]`
Children → Parent	Tree DP	`dp[node][state]`
DAG dependencies	Graph DP	`dp[node]`
Used subset	Bitmask DP	`dp[mask][i]`
Digit constraints	Digit DP	`dp[pos][state...]`

7. What to Master First for Interviews

You don't need to master every pattern equally.

Tier 1 — Essential

1. 1D DP
2. 0/1 Knapsack
3. Unbounded Knapsack
4. LCS
5. Grid DP
6. LIS

Tier 2 — Very Important

7. State Machine DP
8. Interval / MCM DP
9. Tree DP

Tier 3 — Advanced

10. DAG DP
11. Bitmask DP
12. Digit DP

8. How to Practice Each Pattern

For every pattern, solve problems using the same learning sequence:

                  PROBLEM
                     │
                     ↓
             Identify the state
                     │
                     ↓
            Are there choices?
                 /       \
               YES        NO
                ↓          ↓
          Identify      Identify
           choices      dependency
                \          /
                 ↓        ↓
                  RECURSION
                      ↓
            EXPLICIT MEMO TABLE
                      ↓
          Understand each cell
                      ↓
             Find dependencies
                      ↓
             Bottom-Up DP
                      ↓
              Optimize Space

Do not immediately jump to the optimized solution.

If you can write:

solve(...)

and explain exactly what it means, you are already most of the way there.

9. The Real Goal

The biggest leap in DP comes when you stop asking:

"Have I seen this exact problem before?"

and start asking:

"What is the state, and how can I derive it?"

Consider these problems:

House Robber
Counting Bits
Knapsack
LCS
Stock Trading
Matrix Chain Multiplication
TSP

They look completely different.

But their states are:

House Robber
    → dp[i]
 
Counting Bits
    → dp[i]
 
Knapsack
    → dp[i][capacity]
 
LCS
    → dp[i][j]
 
Stock
    → dp[i][holding]
 
MCM
    → dp[i][j]
 
TSP
    → dp[mask][city]

And the reasoning is always:

Identify State
      ↓
Find Choices OR Dependencies
      ↓
Write Recursion
      ↓
Add Explicit Memoization
      ↓
Understand Memo Table
      ↓
Determine Dependencies
      ↓
Choose Iteration Order
      ↓
Convert to Tabulation
      ↓
Optimize Space

That is the skill that turns Dynamic Programming from a collection of tricks into a repeatable problem-solving process.

10. Final Takeaway

The most important thing to remember is:

DP is not synonymous with take/skip.

take/skip is just one very common way of creating a recurrence.

The real DP process is:

                 DEFINE STATE
                      ↓
             FIND RELATIONSHIP
                      ↓
          ┌───────────┴───────────┐
          ↓                       ↓
     CHOICES EXIST          NO CHOICE
          ↓                       ↓
    take / skip / etc.       dependency
          │                       │
          └───────────┬───────────┘
                      ↓
                  RECURSION
                      ↓
             EXPLICIT MEMO
                      ↓
              DP TABLE
                      ↓
           DEPENDENCY ORDER
                      ↓
           SPACE OPTIMIZATION

If you learn to identify the state and its dependency, rather than memorizing take/skip, you will be able to recognize a much larger class of DP problems.

The question to ask in an interview is not:

"What is the DP template?"

It is:

"What does dp[state] mean, and which smaller states do I need to calculate it?"

Once you can answer that, the rest of the solution usually follows.

Related