LeetCode Patterns ·

🎯 Dynamic Programming Intro

1️⃣ Core Framework

When discussing Dynamic Programming, I frame it as:

What problem pattern DP solves
Overlapping subproblems
Optimal substructure
State definition
Recurrence relation
Base cases
Top-down memoization
Bottom-up tabulation
Space optimization
Senior-level explanation

2️⃣ What Problem Are We Solving?

Dynamic programming is used when a problem can be broken into smaller subproblems, and those subproblems repeat.

It is commonly used for:

Fibonacci-style problems
Climbing stairs
House robber
Coin change
Longest increasing subsequence
Longest common subsequence
Knapsack
Grid path problems
Edit distance
Palindrome DP
Stock buy/sell problems

The core idea is:

Solve each subproblem once.
Store its result.
Reuse it later.

👉 Interview Answer

Dynamic programming is a technique for solving problems with overlapping subproblems and optimal substructure.

Instead of recomputing the same subproblem many times, we store previous results and reuse them.

The key is to define the state, derive the recurrence, set base cases, and choose either top-down memoization or bottom-up tabulation.

3️⃣ Why Dynamic Programming Works

Brute Force Recursion Problem

Take Fibonacci:

fib(n) = fib(n - 1) + fib(n - 2)

Naive recursion:

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

This recomputes the same values many times.

Example:

fib(5)
= fib(4) + fib(3)

fib(4)
= fib(3) + fib(2)

fib(3) is computed more than once.

DP Optimization

Instead of recomputing:

compute fib(3) once
store it
reuse it

This changes complexity from exponential to linear.

👉 Interview Answer

Dynamic programming works because many recursive solutions repeatedly solve the same subproblems.

DP stores the result of each subproblem.

When the same subproblem appears again, we return the cached value instead of recomputing it.

This can reduce exponential recursion to polynomial or linear time.

4️⃣ Two Required Conditions

1. Overlapping Subproblems

The same subproblem appears multiple times.

Example:

fib(5) needs fib(3)
fib(4) also needs fib(3)

2. Optimal Substructure

The answer to the original problem can be built from answers to smaller subproblems.

Example:

fib(n) = fib(n - 1) + fib(n - 2)

If These Conditions Hold

Dynamic programming is likely a good fit.

👉 Interview Answer

DP usually applies when two conditions exist.

First, overlapping subproblems: the same smaller problems are solved repeatedly.

Second, optimal substructure: the answer to a larger problem can be built from answers to smaller problems.

If both conditions are present, DP is often a strong candidate.

5️⃣ The DP Design Process

Step-by-Step

When solving a DP problem, I usually ask:

What is the state?
What does dp[i] mean?
What is the recurrence?
What are the base cases?
What is the iteration order?
Can space be optimized?

Most Important Question

What does dp[i] represent?

If the state definition is wrong, the recurrence usually becomes confusing.

👉 Interview Answer

My first step in DP is defining the state clearly.

I ask what dp[i] or dp[i][j] represents in plain English.

Then I derive the recurrence from smaller states, define base cases, decide iteration order, and finally consider whether space can be optimized.

6️⃣ State Definition

What Is State?

A state describes a subproblem.

Example:

dp[i] = answer for the first i elements

or:

dp[i] = answer ending at index i

or:

dp[i][j] = answer using first i characters of s and first j characters of t

Good State Definition

A good state should answer:

What smaller problem am I solving?
What information do I need to make the next decision?

👉 Interview Answer

A DP state represents a subproblem.

For example, dp[i] may mean the best answer using the first i elements, or the best answer ending at index i.

The state must contain enough information to transition to future states without needing full history.

7️⃣ Recurrence Relation

What Is Recurrence?

A recurrence describes how to compute the current state from previous states.

Example:

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

For climbing stairs:

ways to reach step i
= ways from i - 1
+ ways from i - 2

Key Idea

The recurrence answers:

How do smaller subproblems combine into the current subproblem?

👉 Interview Answer

The recurrence relation defines how one DP state is computed from smaller states.

Once I define what dp[i] means, I ask how dp[i] can be built from previous states.

This is usually the core of the DP solution.

8️⃣ Base Cases

Why Base Cases Matter

Base cases initialize the smallest subproblems.

Example:

fib(0) = 0
fib(1) = 1

For climbing stairs:

dp[0] = 1
dp[1] = 1

Common Mistake

Incorrect base cases often cause:

off-by-one errors
wrong answers for small inputs
index out of range

👉 Interview Answer

Base cases define the smallest valid subproblems.

They are necessary because every recurrence eventually depends on them.

I always test DP solutions on small inputs to verify the base cases.

9️⃣ Top-Down DP With Memoization

Core Idea

Start from the original problem.

Use recursion.

Cache results.

Fibonacci Code

def fib(n):
    memo = {}

    def dfs(x):
        if x <= 1:
            return x

        if x in memo:
            return memo[x]

        memo[x] = dfs(x - 1) + dfs(x - 2)
        return memo[x]

    return dfs(n)

Why It Works

The recursion explores only needed states.

The memo prevents recomputation.

👉 Interview Answer

Top-down DP uses recursion plus memoization.

I write the recursive solution naturally, then cache each subproblem result.

This is often easier to derive because it follows the original recurrence directly.

🔟 Bottom-Up DP With Tabulation

Core Idea

Start from base cases.

Build up to the final answer.

Fibonacci Code

def fib(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Why It Works

Every state is computed after its dependencies are already known.

👉 Interview Answer

Bottom-up DP starts from base cases and iteratively fills the DP table.

It avoids recursion overhead and gives explicit control over iteration order.

The key requirement is that when computing a state, all states it depends on have already been computed.

1️⃣1️⃣ Top-Down vs Bottom-Up

Top-Down

Good when:

recurrence is easier to express recursively
not all states may be needed
state space is sparse

Bottom-Up

Good when:

iteration order is clear
want to avoid recursion depth
all states are needed
space optimization is easier

Comparison

Approach	Style	Strength
Top-Down	Recursion + memo	Easier to derive
Bottom-Up	Iteration + table	Often faster and avoids recursion depth

👉 Interview Answer

Top-down DP is often easier to write because it follows the recursive recurrence directly.

Bottom-up DP is often more efficient in practice because it avoids recursion overhead and makes iteration order explicit.

I choose based on which version is easier and safer for the problem.

1️⃣2️⃣ Climbing Stairs

Problem

You can climb either 1 or 2 steps.

How many distinct ways are there to reach step n?

State Definition

dp[i] = number of ways to reach step i

Recurrence

To reach step i:

come from step i - 1
or
come from step i - 2

So:

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

Code

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

👉 Interview Answer

For Climbing Stairs, I define dp[i] as the number of ways to reach step i.

To reach step i, the previous move must come from i - 1 or i - 2.

Therefore, dp[i] equals dp[i - 1] plus dp[i - 2].

1️⃣3️⃣ Space Optimization

Observation

For Fibonacci or Climbing Stairs:

dp[i] only depends on dp[i - 1] and dp[i - 2]

So we do not need the full array.

Code

def climb_stairs(n):
    if n <= 2:
        return n

    prev2 = 1
    prev1 = 2

    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

Complexity

Time: O(n)
Space: O(1)

👉 Interview Answer

If a DP state only depends on a fixed number of previous states, we can optimize space.

For Climbing Stairs, dp[i] only depends on dp[i - 1] and dp[i - 2], so two variables are enough.

This reduces space from O(n) to O(1).

1️⃣4️⃣ House Robber

Problem

Given houses with money, you cannot rob two adjacent houses.

Return the maximum money you can rob.

State Definition

dp[i] = maximum money we can rob from houses 0 to i

Decision

At house i:

rob house i:
    nums[i] + dp[i - 2]

skip house i:
    dp[i - 1]

Recurrence

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

Code

def rob(nums):
    if not nums:
        return 0

    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

👉 Interview Answer

For House Robber, I define dp[i] as the maximum money that can be robbed from houses up to index i.

At each house, I have two choices: skip it and keep dp[i - 1], or rob it and add nums[i] to dp[i - 2].

The recurrence is the maximum of those two choices.

1️⃣5️⃣ Coin Change

Problem

Given coins and amount, return the fewest number of coins needed to make up that amount.

If impossible, return -1.

State Definition

dp[x] = minimum number of coins needed to make amount x

Recurrence

For each coin:

dp[x] = min(dp[x], dp[x - coin] + 1)

Code

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for coin in coins:
            if x - coin >= 0:
                dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

👉 Interview Answer

For Coin Change, I define dp[x] as the minimum number of coins needed to make amount x.

For each amount x, I try every coin.

If coin can be used, then dp[x - coin] + 1 is a candidate answer.

I take the minimum over all coins.

1️⃣6️⃣ 0/1 Knapsack Intro

Problem Pattern

Given items with weights and values, choose items to maximize value without exceeding capacity.

Each item can be used at most once.

State Definition

dp[i][c] = maximum value using first i items with capacity c

Decision

For item i:

skip item i
take item i if capacity allows

Recurrence

dp[i][c] = max(
    dp[i - 1][c],
    dp[i - 1][c - weight[i]] + value[i]
)

👉 Interview Answer

0/1 Knapsack is a classic DP pattern.

The state represents the best value using a prefix of items and a given capacity.

For each item, we either skip it or take it if there is enough capacity.

Since each item can be used once, the transition comes from the previous item row.

1️⃣7️⃣ Grid DP Intro

Problem Pattern

Move from top-left to bottom-right.

Usually can move:

right
down

State Definition

dp[r][c] = number of ways to reach cell (r, c)

Recurrence

To reach (r, c):

come from top
or
come from left

So:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Code

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]

    for r in range(m):
        dp[r][0] = 1

    for c in range(n):
        dp[0][c] = 1

    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]

👉 Interview Answer

For grid DP, I usually define dp[r][c] as the answer for reaching or optimizing at cell r, c.

If movement is only down and right, then each cell can only be reached from the top or left.

This gives the recurrence dp[r][c] = dp[r - 1][c] + dp[r][c - 1].

1️⃣8️⃣ 1D DP vs 2D DP

1D DP

Use when state depends on one variable.

Examples:

index
amount
step
capacity

Examples:

Climbing Stairs
House Robber
Coin Change

2D DP

Use when state depends on two variables.

Examples:

two indexes
index + capacity
row + column
left + right

Examples:

Grid DP
Knapsack
Longest Common Subsequence
Edit Distance
Palindrome DP

👉 Interview Answer

I use 1D DP when the subproblem can be described by one variable, such as index, amount, or step.

I use 2D DP when the state needs two dimensions, such as two strings, grid coordinates, or item index plus capacity.

The dimensions of the DP table should match the information needed to define a subproblem.

1️⃣9️⃣ Memoization Pattern

General Template

from functools import lru_cache

def solve(input_data):
    @lru_cache(None)
    def dfs(state):
        if base_case:
            return base_value

        answer = initial_value

        for choice in choices:
            answer = combine(answer, dfs(next_state))

        return answer

    return dfs(start_state)

Why `lru_cache` Helps

It automatically caches function results by arguments.

Useful for:

recursive DP
state search
string DP
tree-like recurrence

👉 Interview Answer

For top-down DP in Python, I often use lru_cache to memoize recursive states.

The function arguments define the state.

As long as those arguments are hashable, the cache prevents recomputing the same subproblem.

2️⃣0️⃣ Common DP Patterns

Fibonacci Pattern

dp[i] depends on previous few states

Examples:

Climbing Stairs
House Robber
Min Cost Climbing Stairs

Knapsack Pattern

choose or skip items under capacity constraint

Examples:

0/1 Knapsack
Partition Equal Subset Sum
Target Sum

Grid Pattern

dp[r][c] depends on neighboring cells

Examples:

Unique Paths
Minimum Path Sum
Dungeon Game

Two-String Pattern

dp[i][j] depends on prefixes of two strings

Examples:

Longest Common Subsequence
Edit Distance
Interleaving String

Interval Pattern

dp[left][right] represents answer for a subarray or substring

Examples:

Palindrome Substrings
Burst Balloons
Matrix Chain Multiplication

👉 Interview Answer

Many DP problems fall into recognizable patterns.

Fibonacci-style DP depends on previous states.

Knapsack DP involves choose-or-skip decisions.

Grid DP depends on neighboring cells.

Two-string DP uses two indexes.

Interval DP solves subarray or substring ranges.

Recognizing the pattern helps define the state faster.

2️⃣1️⃣ Common Edge Cases

Empty Input

nums = []
s = ""
amount = 0

Single Element

nums = [x]
n = 1

Zero State

dp[0]
amount = 0
empty prefix

Impossible State

Use:

infinity
-1
None

depending on the problem.

Negative Index

Be careful with:

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

👉 Interview Answer

Common DP edge cases include empty input, single element, zero state, impossible states, and negative index access.

I usually test DP solutions with the smallest inputs first, because base-case errors are common.

2️⃣2️⃣ Common Mistakes

Mistake 1: Unclear State Definition

If dp[i] is not clearly defined, the recurrence becomes confusing.

Mistake 2: Wrong Base Case

Bad base cases cause wrong answers for small inputs.

Mistake 3: Wrong Iteration Order

If a state depends on previous states, those states must be computed first.

Mistake 4: Off-by-One Errors

Common when using:

first i elements
index i
prefix length i

Mistake 5: Incorrect Space Optimization

Optimizing space before understanding dependencies can break the solution.

Mistake 6: Confusing Greedy With DP

If local optimal choices are not always globally optimal, DP may be needed.

👉 Interview Answer

Common DP mistakes include unclear state definition, wrong base cases, incorrect iteration order, off-by-one errors, unsafe space optimization, and confusing greedy problems with DP problems.

I avoid these by first writing a clear state meaning in plain English.

2️⃣3️⃣ When DP Applies

Good Fit

Use DP when the problem has:

overlapping subproblems
optimal substructure
count ways
minimum or maximum value
choose or skip decisions
sequence optimization
grid optimization
prefix-based recurrence

Problem Signals

Look for words like:

minimum
maximum
count number of ways
can be formed
longest
shortest under choices
choose or skip
ways to reach
optimal value

👉 Interview Answer

I consider DP when the problem asks for an optimal value, number of ways, or whether something can be formed under repeated choices.

The strongest signals are overlapping subproblems and a recurrence relation between states.

2️⃣4️⃣ When DP Does Not Apply

Not Good Fit

DP may not be ideal when:

no overlapping subproblems
simple local greedy choice works
need shortest path in graph
need all solutions explicitly
state space is too large

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted graph	BFS
Weighted shortest path	Dijkstra
Generate all solutions	Backtracking
Local optimal always works	Greedy
Range queries	Prefix Sum / Segment Tree
Connectivity	DFS / Union Find

👉 Interview Answer

DP is not always the right tool.

If there are no overlapping subproblems, memoization may not help.

If a local greedy choice is provably optimal, greedy is simpler.

If the problem asks for all solutions, backtracking may be more appropriate.

2️⃣5️⃣ Standard Templates

Top-Down Memoization Template

from functools import lru_cache

def solve():
    @lru_cache(None)
    def dfs(state):
        if base_case:
            return base_value

        answer = initial_value

        for choice in choices:
            next_state = transition(state, choice)
            answer = combine(answer, dfs(next_state))

        return answer

    return dfs(start_state)

Bottom-Up 1D DP Template

def solve(nums):
    n = len(nums)
    dp = [0] * (n + 1)

    dp[0] = base_value

    for i in range(1, n + 1):
        dp[i] = transition_from_previous_states(dp, i)

    return dp[n]

Bottom-Up 2D DP Template

def solve(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            dp[i][j] = transition(dp, i, j)

    return dp[m][n]

Choose or Skip Template

def solve(nums):
    n = len(nums)
    dp = [0] * n

    for i in range(n):
        skip = dp[i - 1]
        choose = nums[i] + dp[i - 2]
        dp[i] = max(skip, choose)

    return dp[-1]

Grid DP Template

def grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = initial_value

    for r in range(rows):
        for c in range(cols):
            dp[r][c] = combine_from_neighbors(dp, r, c)

    return dp[rows - 1][cols - 1]

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Dynamic programming is a technique for solving problems with overlapping subproblems and optimal substructure.

The main idea is to solve each subproblem once, store its result, and reuse it when needed.

This avoids repeated computation and often reduces exponential recursion to polynomial or linear time.

The first and most important step is defining the state. A DP state represents a smaller subproblem. For example, dp[i] may represent the best answer using the first i elements, the number of ways to reach step i, or the best answer ending at index i.

After defining the state, I derive the recurrence relation. The recurrence explains how to compute the current state from smaller states.

Then I define the base cases, because every recurrence eventually depends on the smallest subproblems.

There are two common implementation styles.

Top-down DP uses recursion with memoization. It is often easier to derive because it follows the natural recursive structure. The cache prevents recomputing the same state.

Bottom-up DP starts from base cases and fills a table iteratively. It avoids recursion overhead and makes iteration order explicit.

Space optimization is possible when each state only depends on a fixed number of previous states. For example, Climbing Stairs only needs the previous two values, so the DP array can be reduced to two variables.

Many DP problems fall into common patterns. Fibonacci-style DP depends on previous states. Knapsack DP involves choose-or-skip decisions. Grid DP depends on neighboring cells. Two-string DP uses two indexes. Interval DP solves subarray or substring ranges.

The complexity depends on the number of states times the cost of computing each state. A useful way to analyze DP is: number of states multiplied by transition cost.

At a senior level, I would explain: what the state means, why the problem has overlapping subproblems, what recurrence connects the states, what the base cases are, what iteration order is valid, and whether space can be optimized safely.

⭐ Final Insight

Dynamic Programming 的核心不是“背公式”。

它的核心是把一个大问题拆成 reusable subproblems。

Senior-level 的重点是：

state 代表什么， recurrence 怎么来， base case 是什么， iteration order 为什么正确，有多少 states，每个 state 的 transition cost 是多少，以及能不能安全地 optimize space。

能讲清楚这些， DP 就不是玄学，而是一种系统化建模和复用子问题答案的方法。

中文部分

🎯 Dynamic Programming Intro

1️⃣ 核心框架

讨论 Dynamic Programming 时，我通常从：

DP 解决什么问题
Overlapping subproblems
Optimal substructure
State definition
Recurrence relation
Base cases
Top-down memoization
Bottom-up tabulation
Space optimization
高级工程师解释方式

2️⃣ 要解决什么问题？

Dynamic programming 用于一个问题可以被拆成更小的子问题，并且这些子问题会重复出现的场景。

它常用于：

Fibonacci-style problems
Climbing stairs
House robber
Coin change
Longest increasing subsequence
Longest common subsequence
Knapsack
Grid path problems
Edit distance
Palindrome DP
Stock buy/sell problems

核心思想是：

每个 subproblem 只解决一次。
把结果存起来。
之后重复使用。

👉 面试回答

Dynamic programming 是一种用于解决 overlapping subproblems 和 optimal substructure 的技术。

它避免重复计算相同 subproblem，通过存储之前的结果来复用答案。

核心步骤是：定义 state，推导 recurrence，设置 base cases，然后选择 top-down memoization 或 bottom-up tabulation。

3️⃣ 为什么 Dynamic Programming 有效？

暴力递归的问题

以 Fibonacci 为例：

fib(n) = fib(n - 1) + fib(n - 2)

Naive recursion:

def fib(n):
    if n <= 1:
        return n

    return fib(n - 1) + fib(n - 2)

它会重复计算大量相同结果。

Example:

fib(5)
= fib(4) + fib(3)

fib(4)
= fib(3) + fib(2)

fib(3) 被计算多次。

DP 优化

不要重复计算：

compute fib(3) once
store it
reuse it

这样可以把 exponential complexity 降到 linear。

👉 面试回答

DP 有效，是因为很多 recursive solutions 会反复求解相同的 subproblem。

DP 把每个 subproblem 的结果保存起来。

当同一个 subproblem 再次出现时，直接返回 cached value，而不是重新计算。

这通常可以把 exponential recursion 优化成 polynomial 或 linear time。

4️⃣ 两个必要条件

1. Overlapping Subproblems

同一个 subproblem 会多次出现。

Example:

fib(5) needs fib(3)
fib(4) also needs fib(3)

2. Optimal Substructure

大问题的答案可以由小问题的答案构成。

Example:

fib(n) = fib(n - 1) + fib(n - 2)

如果两个条件都存在

Dynamic programming 通常是 strong candidate。

👉 面试回答

DP 通常需要两个条件。

第一是 overlapping subproblems，也就是相同的小问题会被反复求解。

第二是 optimal substructure，也就是大问题答案可以由小问题答案构造出来。

如果这两个条件存在， DP 往往是合适的解法。

5️⃣ DP 设计流程

Step-by-Step

解决 DP 问题时，我通常问：

State 是什么？
dp[i] 表示什么？
Recurrence 是什么？
Base cases 是什么？
Iteration order 是什么？
是否可以 space optimize？

最重要的问题

dp[i] 代表什么？

如果 state definition 不清楚， recurrence 通常就会很混乱。

👉 面试回答

我做 DP 的第一步是清楚定义 state。

我会用自然语言说明 dp[i] 或 dp[i][j] 到底表示什么。

然后从 smaller states 推导 recurrence，定义 base cases，决定 iteration order，最后再考虑能不能 optimize space。

6️⃣ State Definition

什么是 State？

State 描述的是一个 subproblem。

Example:

dp[i] = first i elements 的答案

或者：

dp[i] = ending at index i 的答案

或者：

dp[i][j] = s 的前 i 个字符和 t 的前 j 个字符对应的答案

好的 State Definition

一个好的 state 应该回答：

我在解决什么 smaller problem？
我做下一步 decision 需要什么信息？

👉 面试回答

DP state 表示一个 subproblem。

例如 dp[i] 可以表示使用前 i 个元素的最佳答案，或者表示以 index i 结尾的最佳答案。

State 必须包含足够信息，让我们不需要完整历史就能 transition 到后续状态。

7️⃣ Recurrence Relation

什么是 Recurrence？

Recurrence 描述如何从 previous states 计算 current state。

Example:

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

对于 climbing stairs：

到达 step i 的 ways
= 从 i - 1 上来
+ 从 i - 2 上来

所以：

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

Key Idea

Recurrence 回答：

小问题如何组合成当前问题？

👉 面试回答

Recurrence relation 定义了一个 DP state 如何从 smaller states 计算出来。

一旦我定义清楚 dp[i] 的含义，我就会问： dp[i] 可以由哪些 previous states 构成？

这通常是 DP 解法的核心。

8️⃣ Base Cases

为什么 Base Cases 重要？

Base cases 初始化最小的 subproblems。

Example:

fib(0) = 0
fib(1) = 1

Climbing stairs：

dp[0] = 1
dp[1] = 1

常见问题

Base case 错误通常会导致：

off-by-one errors
small input wrong answer
index out of range

👉 面试回答

Base cases 定义最小的 valid subproblems。

它们很重要，因为所有 recurrence 最终都会依赖 base cases。

我通常会用最小输入测试 DP 解法，来验证 base cases 是否正确。

9️⃣ Top-Down DP With Memoization

Core Idea

从原问题出发。

使用 recursion。

缓存结果。

Fibonacci Code

def fib(n):
    memo = {}

    def dfs(x):
        if x <= 1:
            return x

        if x in memo:
            return memo[x]

        memo[x] = dfs(x - 1) + dfs(x - 2)
        return memo[x]

    return dfs(n)

为什么有效？

Recursion 只探索需要的 states。

Memo 避免重复计算。

👉 面试回答

Top-down DP 使用 recursion 加 memoization。

我先自然地写出 recursive solution，然后缓存每个 subproblem 的结果。

这种方式通常更容易推导，因为它直接跟 recurrence 对应。

🔟 Bottom-Up DP With Tabulation

Core Idea

从 base cases 开始。

一步一步构造到最终答案。

Fibonacci Code

def fib(n):
    if n <= 1:
        return n

    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

为什么有效？

计算每个 state 时，它依赖的 states 已经计算好了。

👉 面试回答

Bottom-up DP 从 base cases 开始，迭代填充 DP table。

它避免 recursion overhead，并且 iteration order 更明确。

核心要求是：当我们计算当前 state 时，它依赖的 states 已经被计算过。

1️⃣1️⃣ Top-Down vs Bottom-Up

Top-Down

适合：

recurrence is easier to express recursively
not all states may be needed
state space is sparse

Bottom-Up

适合：

iteration order is clear
want to avoid recursion depth
all states are needed
space optimization is easier

Comparison

Approach	Style	Strength
Top-Down	Recursion + memo	Easier to derive
Bottom-Up	Iteration + table	Often faster and avoids recursion depth

👉 面试回答

Top-down DP 通常更容易写，因为它直接按照 recursive recurrence 来表达。

Bottom-up DP 通常实践中更高效，因为它避免 recursion overhead，并且 iteration order 更明确。

我会根据问题选择更容易、更安全的实现方式。

1️⃣2️⃣ Climbing Stairs

Problem

每次可以爬 1 或 2 个台阶。

问到达 step n 有多少种不同方式。

State Definition

dp[i] = 到达 step i 的 ways

Recurrence

到达 step i 可以来自：

step i - 1
or
step i - 2

所以：

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

Code

def climb_stairs(n):
    if n <= 2:
        return n

    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

👉 面试回答

对 Climbing Stairs，我定义 dp[i] 为到达第 i 阶的方法数。

到达 step i 的最后一步，只能来自 i - 1 或 i - 2。

所以 recurrence 是： dp[i] = dp[i - 1] + dp[i - 2]。

1️⃣3️⃣ Space Optimization

Observation

对 Fibonacci 或 Climbing Stairs：

dp[i] only depends on dp[i - 1] and dp[i - 2]

所以不需要完整 array。

Code

def climb_stairs(n):
    if n <= 2:
        return n

    prev2 = 1
    prev1 = 2

    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

Complexity

Time: O(n)
Space: O(1)

👉 面试回答

如果一个 DP state 只依赖固定数量的 previous states，就可以 optimize space。

对 Climbing Stairs， dp[i] 只依赖 dp[i - 1] 和 dp[i - 2]。

所以两个变量就够了，可以把 space 从 O(n) 降到 O(1)。

1️⃣4️⃣ House Robber

Problem

给定每个 house 的 money，不能 rob 相邻 houses。

返回最多能 rob 多少钱。

State Definition

dp[i] = 从 house 0 到 house i 能 rob 的最大金额

Decision

在 house i：

rob house i:
    nums[i] + dp[i - 2]

skip house i:
    dp[i - 1]

Recurrence

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

Code

def rob(nums):
    if not nums:
        return 0

    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

👉 面试回答

对 House Robber，我定义 dp[i] 为从 0 到 i 的 houses 中能 rob 的最大金额。

对每个 house，有两个选择：不 rob 当前 house，答案是 dp[i - 1]；或者 rob 当前 house，答案是 nums[i] + dp[i - 2]。

取两者最大值。

1️⃣5️⃣ Coin Change

Problem

给定 coins 和 amount，返回组成 amount 所需的最少 coin 数。

如果无法组成，返回 -1。

State Definition

dp[x] = 组成 amount x 所需的最少 coins 数

Recurrence

对每个 coin：

dp[x] = min(dp[x], dp[x - coin] + 1)

Code

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for coin in coins:
            if x - coin >= 0:
                dp[x] = min(dp[x], dp[x - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

👉 面试回答

对 Coin Change，我定义 dp[x] 为组成金额 x 所需的最少 coins 数。

对每个 amount x，我尝试每个 coin。

如果可以使用这个 coin，那么 dp[x - coin] + 1 是一个候选答案。

我在所有候选中取最小值。

1️⃣6️⃣ 0/1 Knapsack Intro

Problem Pattern

给定 items，每个 item 有 weight 和 value。

选择一些 items，在不超过 capacity 的情况下 maximize value。

每个 item 最多使用一次。

State Definition

dp[i][c] = 使用前 i 个 items，capacity 为 c 时的最大 value

Decision

对 item i：

skip item i
take item i if capacity allows

Recurrence

dp[i][c] = max(
    dp[i - 1][c],
    dp[i - 1][c - weight[i]] + value[i]
)

👉 面试回答

0/1 Knapsack 是经典 DP pattern。

State 表示使用一部分 items 和某个 capacity 时能得到的最大 value。

对每个 item，要么 skip，要么在 capacity 允许时 take。

因为每个 item 只能用一次， transition 来自 previous item row。

1️⃣7️⃣ Grid DP Intro

Problem Pattern

从 top-left 移动到 bottom-right。

通常只能走：

right
down

State Definition

dp[r][c] = 到达 cell (r, c) 的 ways

Recurrence

到达 (r, c) 可以来自：

top
or
left

所以：

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

Code

def unique_paths(m, n):
    dp = [[0] * n for _ in range(m)]

    for r in range(m):
        dp[r][0] = 1

    for c in range(n):
        dp[0][c] = 1

    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]

👉 面试回答

对 grid DP，我通常定义 dp[r][c] 为到达或优化到 cell r, c 时的答案。

如果只能向右或向下移动，那么每个 cell 只能从 top 或 left 到达。

因此 recurrence 是： dp[r][c] = dp[r - 1][c] + dp[r][c - 1]。

1️⃣8️⃣ 1D DP vs 2D DP

1D DP

当 state 只依赖一个变量时使用。

Examples:

index
amount
step
capacity

Examples:

Climbing Stairs
House Robber
Coin Change

2D DP

当 state 依赖两个变量时使用。

Examples:

two indexes
index + capacity
row + column
left + right

Examples:

Grid DP
Knapsack
Longest Common Subsequence
Edit Distance
Palindrome DP

👉 面试回答

当 subproblem 可以用一个变量描述时，我使用 1D DP，比如 index、amount 或 step。

当 subproblem 需要两个变量描述时，我使用 2D DP，比如两个字符串、grid coordinates，或者 item index 加 capacity。

DP table 的维度应该匹配 state 需要的信息。

1️⃣9️⃣ Memoization Pattern

General Template

from functools import lru_cache

def solve(input_data):
    @lru_cache(None)
    def dfs(state):
        if base_case:
            return base_value

        answer = initial_value

        for choice in choices:
            answer = combine(answer, dfs(next_state))

        return answer

    return dfs(start_state)

为什么 `lru_cache` 有用？

它会自动根据 function arguments 缓存结果。

适合：

recursive DP
state search
string DP
tree-like recurrence

👉 面试回答

在 Python 中写 top-down DP，我经常使用 lru_cache 来 memoize recursive states。

Function arguments 就是 state。

只要这些 arguments 是 hashable 的， cache 就能防止重复计算相同 subproblem。

2️⃣0️⃣ Common DP Patterns

Fibonacci Pattern

dp[i] depends on previous few states

Examples:

Climbing Stairs
House Robber
Min Cost Climbing Stairs

Knapsack Pattern

choose or skip items under capacity constraint

Examples:

0/1 Knapsack
Partition Equal Subset Sum
Target Sum

Grid Pattern

dp[r][c] depends on neighboring cells

Examples:

Unique Paths
Minimum Path Sum
Dungeon Game

Two-String Pattern

dp[i][j] depends on prefixes of two strings

Examples:

Longest Common Subsequence
Edit Distance
Interleaving String

Interval Pattern

dp[left][right] represents answer for a subarray or substring

Examples:

Palindrome Substrings
Burst Balloons
Matrix Chain Multiplication

👉 面试回答

很多 DP 问题属于固定模式。

Fibonacci-style DP 依赖 previous states。

Knapsack DP 是 choose-or-skip。

Grid DP 依赖相邻 cells。

Two-string DP 使用两个 indexes。

Interval DP 解决 subarray 或 substring 范围。

识别 pattern 可以帮助更快定义 state。

2️⃣1️⃣ 常见 Edge Cases

Empty Input

nums = []
s = ""
amount = 0

Single Element

nums = [x]
n = 1

Zero State

dp[0]
amount = 0
empty prefix

Impossible State

使用：

infinity
-1
None

根据题目选择。

Negative Index

注意：

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

👉 面试回答

DP 常见 edge cases 包括 empty input、 single element、 zero state、 impossible states、以及 negative index access。

我通常先用最小输入测试 DP，因为 base case 错误非常常见。

2️⃣2️⃣ 常见错误

Mistake 1: State Definition 不清楚

如果 dp[i] 含义不明确， recurrence 会很难写对。

Mistake 2: Base Case 错误

Base case 错误会导致小输入答案错。

Mistake 3: Iteration Order 错误

如果 current state 依赖 previous states，必须先计算 dependencies。

Mistake 4: Off-by-One Errors

常见于：

first i elements
index i
prefix length i

Mistake 5: Space Optimization 错误

在没有理解 dependency 前优化 space，很容易破坏正确性。

Mistake 6: Confusing Greedy With DP

如果 local optimal 不一定导致 global optimal，通常需要 DP。

👉 面试回答

DP 常见错误包括： state definition 不清楚、 base cases 错误、 iteration order 错误、 off-by-one、不安全的 space optimization、以及把需要 DP 的问题误判成 greedy。

我通常先用自然语言写清楚 state 的含义。

2️⃣3️⃣ 什么时候 DP 适用？

Good Fit

当问题有：

overlapping subproblems
optimal substructure
count ways
minimum or maximum value
choose or skip decisions
sequence optimization
grid optimization
prefix-based recurrence

Problem Signals

看到这些词想到 DP：

minimum
maximum
count number of ways
can be formed
longest
shortest under choices
choose or skip
ways to reach
optimal value

👉 面试回答

当题目问 optimal value、number of ways，或者在 repeated choices 下能否形成某种结果时，我会考虑 DP。

最强信号是：存在 overlapping subproblems，并且 state 之间能写出 recurrence。

2️⃣4️⃣ 什么时候 DP 不适用？

Not Good Fit

DP 可能不适合：

no overlapping subproblems
simple local greedy choice works
need shortest path in graph
need all solutions explicitly
state space is too large

Better Alternatives

Problem Type	Better Pattern
Shortest path unweighted graph	BFS
Weighted shortest path	Dijkstra
Generate all solutions	Backtracking
Local optimal always works	Greedy
Range queries	Prefix Sum / Segment Tree
Connectivity	DFS / Union Find

👉 面试回答

DP 不是所有问题都适合。

如果没有 overlapping subproblems， memoization 没有帮助。

如果 local greedy choice 可以证明是 optimal， greedy 更简单。

如果题目要求列出所有 solutions， backtracking 通常更合适。

2️⃣5️⃣ 标准模板

Top-Down Memoization Template

from functools import lru_cache

def solve():
    @lru_cache(None)
    def dfs(state):
        if base_case:
            return base_value

        answer = initial_value

        for choice in choices:
            next_state = transition(state, choice)
            answer = combine(answer, dfs(next_state))

        return answer

    return dfs(start_state)

Bottom-Up 1D DP Template

def solve(nums):
    n = len(nums)
    dp = [0] * (n + 1)

    dp[0] = base_value

    for i in range(1, n + 1):
        dp[i] = transition_from_previous_states(dp, i)

    return dp[n]

Bottom-Up 2D DP Template

def solve(a, b):
    m = len(a)
    n = len(b)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            dp[i][j] = transition(dp, i, j)

    return dp[m][n]

Choose or Skip Template

def solve(nums):
    n = len(nums)
    dp = [0] * n

    for i in range(n):
        skip = dp[i - 1]
        choose = nums[i] + dp[i - 2]
        dp[i] = max(skip, choose)

    return dp[-1]

Grid DP Template

def grid_dp(grid):
    rows = len(grid)
    cols = len(grid[0])

    dp = [[0] * cols for _ in range(rows)]

    dp[0][0] = initial_value

    for r in range(rows):
        for c in range(cols):
            dp[r][c] = combine_from_neighbors(dp, r, c)

    return dp[rows - 1][cols - 1]

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Dynamic programming 是一种用于解决 overlapping subproblems 和 optimal substructure 的方法。

它的核心思想是：每个 subproblem 只解决一次，保存结果，之后重复使用。

这样可以避免重复计算，通常把 exponential recursion 优化成 polynomial 或 linear time。

DP 的第一步，也是最重要的一步，是定义 state。 State 表示一个 smaller subproblem。例如， dp[i] 可以表示使用前 i 个元素的最佳答案，到达第 i 阶的方法数，或者以 index i 结尾的最佳答案。

定义 state 之后，我会推导 recurrence relation。 Recurrence 说明当前 state 如何由 smaller states 计算。

然后定义 base cases，因为所有 recurrence 最终都依赖最小子问题。

DP 有两种常见实现方式。

Top-down DP 使用 recursion + memoization。它通常更容易推导，因为它直接对应自然的 recursive structure。 Cache 用来避免重复计算相同 state。

Bottom-up DP 从 base cases 开始，迭代填充 table。它避免 recursion overhead，并且 iteration order 更明确。

当一个 state 只依赖固定数量的 previous states 时，可以进行 space optimization。比如 Climbing Stairs 只依赖前两个值，所以可以把 DP array 优化成两个变量。

很多 DP 问题有固定模式。 Fibonacci-style DP 依赖 previous states。 Knapsack DP 是 choose-or-skip。 Grid DP 依赖 neighboring cells。 Two-string DP 使用两个 indexes。 Interval DP 解决 subarray 或 substring ranges。

DP 的复杂度取决于： number of states × transition cost。

高级工程师解释 DP 时，我会讲清楚： state 表示什么，为什么问题有 overlapping subproblems， recurrence 如何连接 states， base cases 是什么， iteration order 为什么正确，以及 space 是否可以安全优化。

⭐ Final Insight

Dynamic Programming 的核心不是“背公式”。

它的核心是把大问题拆成 reusable subproblems。

Senior-level 的重点是：

state 代表什么， recurrence 怎么来， base case 是什么， iteration order 为什么正确，有多少 states，每个 state 的 transition cost 是多少，以及能不能安全地 optimize space。

能讲清楚这些， DP 就不是玄学，而是一种系统化建模和复用子问题答案的方法。

🎯 Dynamic Programming Intro

1️⃣ Core Framework

2️⃣ What Problem Are We Solving?

3️⃣ Why Dynamic Programming Works

Brute Force Recursion Problem

DP Optimization

4️⃣ Two Required Conditions

1. Overlapping Subproblems

2. Optimal Substructure

If These Conditions Hold

5️⃣ The DP Design Process

Step-by-Step

Most Important Question

6️⃣ State Definition

What Is State?

Good State Definition

7️⃣ Recurrence Relation

What Is Recurrence?

Key Idea

8️⃣ Base Cases

Why Base Cases Matter

Common Mistake

9️⃣ Top-Down DP With Memoization

Core Idea

Fibonacci Code

Why It Works

🔟 Bottom-Up DP With Tabulation

Core Idea

Fibonacci Code

Why It Works

1️⃣1️⃣ Top-Down vs Bottom-Up

Top-Down

Bottom-Up

Comparison

1️⃣2️⃣ Climbing Stairs

Problem

State Definition

Recurrence

Code

1️⃣3️⃣ Space Optimization

Observation

Code

Complexity

1️⃣4️⃣ House Robber

Problem

State Definition

Decision

Recurrence

Code

1️⃣5️⃣ Coin Change

Problem

State Definition

Recurrence

Code

1️⃣6️⃣ 0/1 Knapsack Intro

Problem Pattern

State Definition

Decision

Recurrence

1️⃣7️⃣ Grid DP Intro

Problem Pattern

State Definition

Recurrence

Code

1️⃣8️⃣ 1D DP vs 2D DP

1D DP

2D DP

1️⃣9️⃣ Memoization Pattern

General Template

Why lru_cache Helps

2️⃣0️⃣ Common DP Patterns

Fibonacci Pattern

Knapsack Pattern

Grid Pattern

Two-String Pattern

Interval Pattern

2️⃣1️⃣ Common Edge Cases

Empty Input

Single Element

Zero State

Why `lru_cache` Helps