LeetCode Patterns ·

🎯 DP - Sequence

1️⃣ Core Framework

When discussing Sequence DP, I frame it as:

What problem pattern sequence DP solves
DP on index
DP ending at index
DP using first i elements
Longest increasing subsequence
Maximum subarray
Word break
Decode ways
Common edge cases
Senior-level explanation

2️⃣ What Problem Are We Solving?

Sequence DP is used when the input is an ordered sequence and the answer depends on previous positions.

It is commonly used for:

Maximum Subarray
Longest Increasing Subsequence
Longest Continuous Increasing Subsequence
Word Break
Decode Ways
House Robber
Jump Game variants
Paint House
Min Cost Climbing Stairs
Arithmetic slices
Longest alternating subsequence

The core idea is:

Use previous positions to compute the best answer at the current position.

👉 Interview Answer

Sequence DP is used when the input has a natural order, such as an array or string, and the answer at one position depends on earlier positions.

The key is to define what dp[i] means: either the answer using the first i elements, or the answer ending exactly at index i.

Once the state is clear, the recurrence usually follows from how the current element extends previous states.

3️⃣ Two Common State Definitions

Pattern 1: Using First i Elements

dp[i] = answer using the first i elements

This is common when the current state represents a prefix.

Examples:

Word Break
Decode Ways
Min Cost Climbing Stairs
House Robber

Pattern 2: Ending at Index i

dp[i] = best answer ending exactly at index i

This is common when the answer must include the current element.

Examples:

Maximum Subarray
Longest Increasing Subsequence
Longest Continuous Increasing Subsequence
Arithmetic Slices

👉 Interview Answer

In sequence DP, I first decide whether dp[i] means the answer for the prefix ending before i, or the answer ending exactly at index i.

Prefix-style DP is useful for string segmentation and counting ways.

Ending-at-index DP is useful when the current element must be part of the subproblem.

4️⃣ Why State Meaning Matters

Example: Maximum Subarray

For Maximum Subarray:

dp[i] = maximum subarray sum ending exactly at index i

Why ending exactly at i?

Because a subarray is contiguous.

At index i, we either:

start new subarray at i
extend previous subarray ending at i - 1

Example: Word Break

For Word Break:

dp[i] = whether s[0:i] can be segmented

Why prefix?

Because we need to know whether the prefix before the current word is valid.

👉 Interview Answer

The same dp[i] notation can mean different things.

For maximum subarray, dp[i] means the best subarray ending exactly at i.

For word break, dp[i] means whether the prefix s[0:i] can be segmented.

Defining this clearly avoids most recurrence mistakes.

5️⃣ Maximum Subarray

Problem

Given an integer array, find the contiguous subarray with the largest sum.

nums = [-2,1,-3,4,-1,2,1,-5,4]
answer = 6

The best subarray is:

[4, -1, 2, 1]

State Definition

dp[i] = maximum subarray sum ending exactly at index i

Recurrence

At index i:

start new subarray at nums[i]
or
extend previous subarray

So:

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

Code

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

    best = dp[0]

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

    return best

👉 Interview Answer

For Maximum Subarray, I define dp[i] as the maximum subarray sum ending exactly at index i.

At each index, I either start a new subarray from nums[i], or extend the previous subarray ending at i - 1.

The global answer is the maximum value among all dp[i].

6️⃣ Kadane’s Algorithm

Space Optimized Version

Since dp[i] only depends on dp[i - 1], we can use one variable.

Code

def max_sub_array(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)

    return best

Complexity

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

👉 Interview Answer

Kadane’s algorithm is the space-optimized version of maximum subarray DP.

The current variable stores the best subarray sum ending at the current index.

The best variable stores the best answer seen so far.

Since only the previous state is needed, the space is O(1).

7️⃣ Longest Increasing Subsequence

Problem

Given an array, return the length of the longest strictly increasing subsequence.

nums = [10, 9, 2, 5, 3, 7, 101, 18]
answer = 4

One LIS is:

[2, 3, 7, 101]

State Definition

dp[i] = length of the longest increasing subsequence ending exactly at index i

Recurrence

For every previous index j:

if nums[j] < nums[i],
then nums[i] can extend the subsequence ending at j

So:

dp[i] = max(dp[i], dp[j] + 1)

Code

def length_of_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)

👉 Interview Answer

For Longest Increasing Subsequence, I define dp[i] as the LIS length ending exactly at index i.

To compute dp[i], I check all previous indexes j.

If nums[j] is smaller than nums[i], then nums[i] can extend the subsequence ending at j.

The answer is the maximum dp[i].

8️⃣ LIS Optimized With Binary Search

Key Idea

Maintain an array tails.

tails[length - 1] = smallest possible ending value of an increasing subsequence of that length

Example

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

We keep replacing with smaller tails when possible.

This does not store the actual sequence, but it stores enough information to compute the length.

Code

import bisect

def length_of_lis(nums):
    tails = []

    for num in nums:
        index = bisect.bisect_left(tails, num)

        if index == len(tails):
            tails.append(num)
        else:
            tails[index] = num

    return len(tails)

Complexity

Time: O(n log n)
Space: O(n)

👉 Interview Answer

The optimized LIS algorithm uses binary search.

The tails array stores the smallest possible tail value for increasing subsequences of each length.

For each number, I use binary search to find where it should replace or extend tails.

This gives O(n log n) time.

9️⃣ Longest Continuous Increasing Subsequence

Problem

Find the longest contiguous increasing subarray.

nums = [1, 3, 5, 4, 7]
answer = 3

The best continuous increasing subarray is:

[1, 3, 5]

State Definition

dp[i] = length of longest continuous increasing subarray ending at i

Recurrence

If:

nums[i] > nums[i - 1]

then:

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

otherwise:

dp[i] = 1

Code

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

    current = 1
    best = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            current += 1
        else:
            current = 1

        best = max(best, current)

    return best

👉 Interview Answer

For longest continuous increasing subsequence, the sequence must be contiguous.

Therefore, each state only depends on the previous index.

If nums[i] is greater than nums[i - 1], I extend the current run.

Otherwise, I restart the run from length one.

🔟 Word Break

Problem

Given a string and a word dictionary, determine whether the string can be segmented into dictionary words.

s = "leetcode"
wordDict = ["leet", "code"]
answer = True

State Definition

dp[i] = whether s[0:i] can be segmented

Recurrence

For every split point j:

dp[i] = True if dp[j] is True and s[j:i] is in wordDict

Code

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)

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

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

👉 Interview Answer

For Word Break, I define dp[i] as whether the prefix s[0:i] can be segmented into dictionary words.

To compute dp[i], I try every split point j.

If s[0:j] is segmentable and s[j:i] is a dictionary word, then s[0:i] is also segmentable.

1️⃣1️⃣ Word Break Optimization

Why Optimize?

The basic solution checks every split point.

We can optimize using maximum word length.

Code

def word_break(s, word_dict):
    word_set = set(word_dict)
    max_len = max(len(word) for word in word_dict) if word_dict else 0

    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for length in range(1, max_len + 1):
            j = i - length

            if j < 0:
                break

            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

👉 Interview Answer

Word Break can be optimized by limiting the checked substring length.

If the longest dictionary word has length L, then for each i, I only need to check the previous L characters.

This avoids unnecessary split checks.

1️⃣2️⃣ Decode Ways

Problem

Given a string of digits, return how many ways it can be decoded.

Mapping:

A = 1
B = 2
...
Z = 26

Example:

s = "226"
answer = 3

Ways:

2 6  → B B F
6   → V F
26   → B Z

State Definition

dp[i] = number of ways to decode s[0:i]

Recurrence

For position i:

Single digit

If:

s[i - 1] != "0"

then:

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

Two digits

If:

10 <= int(s[i - 2:i]) <= 26

then:

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

Code

def num_decodings(s):
    if not s:
        return 0

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

    dp[0] = 1
    dp[1] = 1 if s[0] != "0" else 0

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

        if one != "0":
            dp[i] += dp[i - 1]

        if 10 <= int(two) <= 26:
            dp[i] += dp[i - 2]

    return dp[n]

👉 Interview Answer

For Decode Ways, I define dp[i] as the number of ways to decode the prefix s[0:i].

At each position, I check whether the last one digit can form a valid character, and whether the last two digits can form a valid character.

The answer is the sum of the valid transitions.

1️⃣3️⃣ Min Cost Climbing Stairs

Problem

You can climb one or two steps. Each step has a cost. Return the minimum cost to reach the top.

State Definition

dp[i] = minimum cost to reach step i

The top is step:

Recurrence

To reach step i:

from i - 1
or
from i - 2

So:

dp[i] = min(
    dp[i - 1] + cost[i - 1],
    dp[i - 2] + cost[i - 2]
)

Code

def min_cost_climbing_stairs(cost):
    n = len(cost)

    dp = [0] * (n + 1)

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

    return dp[n]

👉 Interview Answer

For Min Cost Climbing Stairs, I define dp[i] as the minimum cost to reach step i.

The top is represented as step n.

To reach step i, I can come from i - 1 or i - 2, paying the cost of the step I came from.

So the recurrence takes the minimum of those two choices.

1️⃣4️⃣ House Robber as Sequence DP

Problem

Rob houses in a line. Cannot rob adjacent houses.

State Definition

dp[i] = max money from houses 0 through i

Recurrence

At house i:

skip i:
    dp[i - 1]

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

So:

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]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current

    return prev1

👉 Interview Answer

House Robber is a sequence DP with a choose-or-skip decision.

At each house, I either skip it and keep the previous best, or rob it and add its value to the best from two houses before.

Since only the previous two states are needed, the space can be optimized to O(1).

1️⃣5️⃣ Jump Game

Problem

Given an array where each element is the maximum jump length, determine whether we can reach the last index.

DP State

dp[i] = whether index i is reachable

DP Code

def can_jump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True

    for i in range(n):
        if not dp[i]:
            continue

        furthest = min(n - 1, i + nums[i])

        for j in range(i + 1, furthest + 1):
            dp[j] = True

    return dp[-1]

Greedy Note

This problem has a better greedy solution.

def can_jump(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

👉 Interview Answer

Jump Game can be modeled with DP where dp[i] means whether index i is reachable.

However, the greedy solution is better.

I track the farthest reachable index.

If I ever reach an index beyond farthest, the end is impossible.

Otherwise, I keep extending farthest.

1️⃣6️⃣ Paint House

Problem

There are houses and colors. Each house has a cost for each color. Adjacent houses cannot have the same color. Return the minimum total cost.

State Definition

dp[i][color] = minimum cost to paint houses 0 to i, with house i painted color

Recurrence

For 3 colors:

dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2])
dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2])
dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1])

Code

def min_cost(costs):
    if not costs:
        return 0

    dp = [row[:] for row in costs]

    for i in range(1, len(costs)):
        dp[i][0] += min(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] += min(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] += min(dp[i - 1][0], dp[i - 1][1])

    return min(dp[-1])

👉 Interview Answer

For Paint House, I define dp[i][color] as the minimum cost to paint houses up to i, where house i has the given color.

Since adjacent houses cannot share the same color, the previous house must use a different color.

The answer is the minimum among the last row.

1️⃣7️⃣ Arithmetic Slices

Problem

Count arithmetic subarrays of length at least 3.

A subarray is arithmetic if consecutive differences are equal.

State Definition

dp[i] = number of arithmetic slices ending at index i

Recurrence

If:

nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]

Then:

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

Otherwise:

dp[i] = 0

Code

def number_of_arithmetic_slices(nums):
    n = len(nums)

    if n < 3:
        return 0

    dp = [0] * n
    total = 0

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

        total += dp[i]

    return total

👉 Interview Answer

For Arithmetic Slices, I define dp[i] as the number of arithmetic subarrays ending at index i.

If the last three numbers continue the same difference, then every arithmetic slice ending at i - 1 can be extended, plus one new slice of length three.

So dp[i] equals dp[i - 1] plus one.

1️⃣8️⃣ Longest Alternating Subsequence

Problem

Find the longest subsequence where differences alternate between positive and negative.

State Definition

Use two states:

up[i] = longest alternating subsequence ending at i with last movement up
down[i] = longest alternating subsequence ending at i with last movement down

Space Optimized Code

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

    up = 1
    down = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1

    return max(up, down)

👉 Interview Answer

For alternating sequence problems, I often use two DP states.

One state represents sequences ending with an upward movement, and the other represents sequences ending with a downward movement.

When the current difference is positive, it can extend a previous down state.

When the current difference is negative, it can extend a previous up state.

1️⃣9️⃣ State Choice: Prefix vs Ending

Prefix State

Use prefix state when:

the problem asks whether a prefix can be formed
the answer builds from previous split points
the current position represents length

Examples:

Word Break
Decode Ways
Min Cost Climbing Stairs

Ending State

Use ending state when:

the solution must include current index
we need best sequence ending here
we compare current element with previous elements

Examples:

Maximum Subarray
LIS
Arithmetic Slices
LCIS

👉 Interview Answer

A key sequence DP decision is whether the state is prefix-based or ending-at-index.

Prefix-based states are useful when we are building or validating prefixes.

Ending-at-index states are useful when the current element must be included in the subproblem.

This distinction often determines the recurrence.

2️⃣0️⃣ Complexity Analysis

Common Formula

For sequence DP:

Time = number of states × transition cost

Examples

Maximum Subarray:

states = n
transition = O(1)
time = O(n)

LIS basic DP:

states = n
transition = O(n)
time = O(n²)

Word Break:

states = n
transition = O(n) split points
time = O(n²) plus substring cost

Space Complexity

Usually:

O(n)

or:

O(1)

if only previous states are needed.

👉 Interview Answer

For sequence DP, I analyze complexity as number of states times transition cost.

If each state only checks a constant number of previous states, the solution is usually O(n).

If each state scans all previous positions, the solution is usually O(n²).

Space can often be optimized when only a few previous states are needed.

2️⃣1️⃣ Common Edge Cases

Empty Input

nums = []
s = ""

Single Element

nums = [x]

All Negative Numbers

Important for Maximum Subarray.

The answer should be the largest negative number, not zero.

Leading Zero

Important for Decode Ways.

"06" is invalid

Duplicate Values

Important for LIS.

Strictly increasing means:

nums[j] < nums[i]

not:

nums[j] <= nums[i]

Prefix Empty State

For string DP:

dp[0]

usually represents an empty prefix.

👉 Interview Answer

Common sequence DP edge cases include empty input, single element, all negative numbers, leading zeros in decoding, duplicate values in increasing subsequences, and the meaning of dp[0] for empty prefix problems.

I always test the smallest input first.

2️⃣2️⃣ Common Mistakes

Mistake 1: Unclear dp[i] Meaning

Confusing:

dp[i] = answer ending at i

with:

dp[i] = answer using first i elements

Mistake 2: Wrong Base Case

Examples:

dp[0] for empty prefix
dp[0] for first element

These mean different things.

Mistake 3: Forgetting Global Answer

For ending-at-index DP, the answer is often:

max(dp)

not necessarily:

dp[-1]

Example:

Maximum Subarray
LIS

Mistake 4: Strict vs Non-Strict Comparison

For LIS:

nums[j] < nums[i]

For non-decreasing subsequence:

nums[j] <= nums[i]

Mistake 5: Unsafe Space Optimization

Only optimize after checking dependencies.

👉 Interview Answer

Common sequence DP mistakes include unclear state meaning, wrong base cases, returning dp[-1] when the answer should be max(dp), mishandling strict comparisons, and optimizing space before understanding dependencies.

I avoid these by first writing the state definition in plain English.

2️⃣3️⃣ When Sequence DP Applies

Good Fit

Use sequence DP when:

input is ordered
current answer depends on previous positions
problem asks for longest, maximum, minimum, count, or feasibility
subproblem can be defined by index
prefix or ending-at-index recurrence exists

Problem Signals

Look for words like:

longest
maximum subarray
ways to decode
can be segmented
ending at
prefix
subsequence
subarray
minimum cost
choose or skip in a line

👉 Interview Answer

I consider sequence DP when the input is ordered and the current answer depends on earlier positions.

Common signals include longest subsequence, maximum subarray, decoding ways, string segmentation, minimum cost along a sequence, or choose-or-skip decisions in a line.

2️⃣4️⃣ When Sequence DP Does Not Apply

Not Good Fit

Sequence DP may not be ideal when:

there is no useful order
need shortest path in a graph
need all solutions explicitly
need range query updates
local greedy choice is sufficient

Better Alternatives

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

👉 Interview Answer

Sequence DP is useful when index order matters.

If the problem is really graph shortest path, BFS or Dijkstra may be better.

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

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

2️⃣5️⃣ Standard Templates

Ending-at-Index Template

def sequence_dp_ending(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if can_extend(nums[j], nums[i]):
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Prefix DP Template

def sequence_dp_prefix(s):
    n = len(s)
    dp = [False] * (n + 1)

    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and valid(s[j:i]):
                dp[i] = True
                break

    return dp[n]

Kadane Template

def kadane(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)

    return best

Decode Ways Template

def decode_ways(s):
    n = len(s)
    dp = [0] * (n + 1)

    dp[0] = 1
    dp[1] = 1 if s[0] != "0" else 0

    for i in range(2, n + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]

        if 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]

    return dp[n]

Choose-or-Skip Sequence Template

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

    prev2 = 0
    prev1 = 0

    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current

    return prev1

🧠 Staff-Level Answer Final

👉 Interview Answer Full Version

Sequence DP is used when the input is ordered, such as an array or string, and the answer at the current position depends on previous positions.

The first question is what dp[i] means.

There are two common state definitions.

One is prefix-style: dp[i] represents the answer using the first i elements, or the prefix s[0:i]. This is common in Word Break, Decode Ways, and Min Cost Climbing Stairs.

The other is ending-at-index style: dp[i] represents the best answer ending exactly at index i. This is common in Maximum Subarray, Longest Increasing Subsequence, Longest Continuous Increasing Subsequence, and Arithmetic Slices.

This distinction is important because it determines the recurrence and the final answer.

For Maximum Subarray, dp[i] is the best subarray sum ending at i. At each index, we either start a new subarray or extend the previous one. The final answer is the maximum over all dp[i].

For LIS, dp[i] is the longest increasing subsequence ending at i. We check all previous positions j, and if nums[j] is smaller than nums[i], we can extend dp[j].

For Word Break, dp[i] means whether s[0:i] can be segmented. We try all split points j, and if dp[j] is true and s[j:i] is a dictionary word, then dp[i] is true.

For Decode Ways, dp[i] counts how many ways to decode the prefix s[0:i]. At each position, we check whether the last one digit and last two digits form valid letters.

A common complexity pattern is: number of states multiplied by transition cost. If each state only depends on the previous state, the solution is O(n). If each state scans all previous positions, the solution is usually O(n²).

Space optimization is possible when the recurrence only needs a few previous states.

At a senior level, I would explain: whether the state is prefix-based or ending-at-index, what dp[i] means, how the current element extends previous states, whether the final answer is dp[n] or max(dp), what the base cases are, and whether strict or non-strict comparisons are needed.

⭐ Final Insight

Sequence DP 的核心不是“看到数组就写 dp[i]”。

它的核心是利用 input order，把当前问题和 previous positions 联系起来。

Senior-level 的重点是：

dp[i] 是 prefix answer 还是 ending-at-index answer， current element 是否必须被包含， recurrence 从哪些 previous states 来， final answer 是 dp[n] 还是 max(dp)， base case 如何定义，以及是否可以安全地 optimize space。

能讲清楚这些， Sequence DP 就是一类处理 array/string order、subarray、subsequence 和 prefix decisions 的核心 DP 模型。

中文部分

🎯 DP - Sequence

1️⃣ 核心框架

讨论 Sequence DP 时，我通常从：

Sequence DP 解决什么问题
Index 上的 DP
Ending at index 的 DP
First i elements 的 DP
Longest increasing subsequence
Maximum subarray
Word break
Decode ways
常见 edge cases
高级工程师解释方式

2️⃣ 要解决什么问题？

Sequence DP 用于输入本身有顺序，并且当前位置的答案依赖之前位置的情况。

它常用于：

Maximum Subarray
Longest Increasing Subsequence
Longest Continuous Increasing Subsequence
Word Break
Decode Ways
House Robber
Jump Game variants
Paint House
Min Cost Climbing Stairs
Arithmetic slices
Longest alternating subsequence

核心思想是：

用 previous positions 计算 current position 的答案。

👉 面试回答

Sequence DP 用于 input 有自然顺序的场景，比如 array 或 string。

当前 index 的答案通常依赖之前的 index。

关键是定义 dp[i] 的含义：它是使用前 i 个元素的答案，还是必须以 index i 结尾的答案。

State 一旦清楚， recurrence 通常就来自 current element 如何连接 previous states。

3️⃣ 两种常见 State Definition

Pattern 1: 使用前 i 个元素

dp[i] = 使用前 i 个元素的答案

适用于 prefix 类问题。

Examples:

Word Break
Decode Ways
Min Cost Climbing Stairs
House Robber

Pattern 2: 必须以 index i 结尾

dp[i] = 必须以 index i 结尾的最佳答案

适用于 current element 必须被包含的问题。

Examples:

Maximum Subarray
Longest Increasing Subsequence
Longest Continuous Increasing Subsequence
Arithmetic Slices

👉 面试回答

在 sequence DP 中，我会先判断 dp[i] 是 prefix answer，还是 ending-at-index answer。

Prefix-style DP 适合 string segmentation 和 counting ways。

Ending-at-index DP 适合 current element 必须参与当前 subproblem 的问题。

4️⃣ 为什么 State Meaning 很重要？

Example: Maximum Subarray

对于 Maximum Subarray：

dp[i] = 必须以 index i 结尾的 maximum subarray sum

为什么必须 ending at i？

因为 subarray 是 contiguous。

在 index i，我们只有两个选择：

从 i 开始新 subarray
延续 i - 1 结尾的 subarray

Example: Word Break

对于 Word Break：

dp[i] = s[0:i] 是否可以被 segment

为什么是 prefix？

因为我们需要知道 current word 前面的 prefix 是否 valid。

👉 面试回答

同样是 dp[i]，含义可能完全不同。

Maximum Subarray 中， dp[i] 表示必须以 i 结尾的 best subarray。

Word Break 中， dp[i] 表示 prefix s[0:i] 是否可以被拆分。

先定义清楚含义，可以避免大多数 recurrence 错误。

5️⃣ Maximum Subarray

Problem

给定 integer array，找 sum 最大的 contiguous subarray。

nums = [-2,1,-3,4,-1,2,1,-5,4]
answer = 6

最佳 subarray 是：

[4, -1, 2, 1]

State Definition

dp[i] = 必须以 index i 结尾的 maximum subarray sum

Recurrence

在 index i：

从 nums[i] 开始新 subarray
或者
延续之前以 i - 1 结尾的 subarray

所以：

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

Code

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

    best = dp[0]

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

    return best

👉 面试回答

对 Maximum Subarray，我定义 dp[i] 为必须以 index i 结尾的 maximum subarray sum。

在每个 index，我可以从 nums[i] 开始新的 subarray，也可以延续以 i - 1 结尾的 subarray。

全局答案是所有 dp[i] 中的最大值。

6️⃣ Kadane’s Algorithm

Space Optimized Version

因为 dp[i] 只依赖 dp[i - 1]，所以可以用一个变量。

Code

def max_sub_array(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)

    return best

Complexity

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

👉 面试回答

Kadane’s algorithm 是 Maximum Subarray DP 的 space-optimized version。

current 表示必须以当前 index 结尾的 best subarray sum。

best 表示目前见过的全局最大答案。

因为只需要 previous state，所以 space 可以优化到 O(1)。

7️⃣ Longest Increasing Subsequence

Problem

给定 array，返回最长 strictly increasing subsequence 的长度。

nums = [10, 9, 2, 5, 3, 7, 101, 18]
answer = 4

一个 LIS 是：

[2, 3, 7, 101]

State Definition

dp[i] = 必须以 index i 结尾的 LIS length

Recurrence

对于每个 previous index j：

if nums[j] < nums[i],
then nums[i] can extend subsequence ending at j

所以：

dp[i] = max(dp[i], dp[j] + 1)

Code

def length_of_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)

👉 面试回答

对 Longest Increasing Subsequence，我定义 dp[i] 为必须以 index i 结尾的 LIS length。

计算 dp[i] 时，我检查所有 previous indexes j。

如果 nums[j] 小于 nums[i]， nums[i] 就可以接在以 j 结尾的 subsequence 后面。

答案是 max(dp)。

8️⃣ LIS Binary Search 优化

Key Idea

维护一个 tails array。

tails[length - 1] = 某个长度为 length 的 increasing subsequence 的最小 possible ending value

Example

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

我们不断用更小的 tail 替换旧 tail。

这不一定保存 actual sequence，但足够计算 length。

Code

import bisect

def length_of_lis(nums):
    tails = []

    for num in nums:
        index = bisect.bisect_left(tails, num)

        if index == len(tails):
            tails.append(num)
        else:
            tails[index] = num

    return len(tails)

Complexity

Time: O(n log n)
Space: O(n)

👉 面试回答

LIS 的优化版本使用 binary search。

tails array 记录每种长度的 increasing subsequence 的最小 possible tail。

对每个 number，我用 binary search 找到它应该替换或扩展的位置。

这样可以把时间复杂度优化到 O(n log n)。

9️⃣ Longest Continuous Increasing Subsequence

Problem

找最长 contiguous increasing subarray。

nums = [1, 3, 5, 4, 7]
answer = 3

最佳 continuous increasing subarray 是：

[1, 3, 5]

State Definition

dp[i] = 以 i 结尾的 longest continuous increasing subarray length

Recurrence

如果：

nums[i] > nums[i - 1]

那么：

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

否则：

dp[i] = 1

Code

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

    current = 1
    best = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            current += 1
        else:
            current = 1

        best = max(best, current)

    return best

👉 面试回答

对 longest continuous increasing subsequence，因为必须 contiguous，当前状态只依赖前一个 index。

如果 nums[i] 大于 nums[i - 1]，就延续当前 increasing run。

否则，从当前 index 重新开始，长度为 1。

🔟 Word Break

Problem

给定 string 和 word dictionary，判断 string 是否可以拆分成 dictionary words。

s = "leetcode"
wordDict = ["leet", "code"]
answer = True

State Definition

dp[i] = s[0:i] 是否可以被 segment

Recurrence

对于每个 split point j：

如果 dp[j] 是 True，
并且 s[j:i] 在 wordDict 中，
那么 dp[i] = True

Code

def word_break(s, word_dict):
    word_set = set(word_dict)
    n = len(s)

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

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

👉 面试回答

对 Word Break，我定义 dp[i] 为 prefix s[0:i] 是否可以被 dictionary words 拆分。

为了计算 dp[i]，我尝试所有 split point j。

如果 s[0:j] 可以被拆分，并且 s[j:i] 是 dictionary word，那么 s[0:i] 也可以被拆分。

1️⃣1️⃣ Word Break Optimization

为什么可以优化？

基础解法会检查所有 split point。

我们可以用最长 word length 限制检查范围。

Code

def word_break(s, word_dict):
    word_set = set(word_dict)
    max_len = max(len(word) for word in word_dict) if word_dict else 0

    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for i in range(1, n + 1):
        for length in range(1, max_len + 1):
            j = i - length

            if j < 0:
                break

            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[n]

👉 面试回答

Word Break 可以用 max word length 优化。

如果 dictionary 中最长 word 长度是 L，那么对每个 i，只需要检查前 L 个字符范围内的 split。

这样可以减少不必要的 substring checks。

1️⃣2️⃣ Decode Ways

Problem

给定 digit string，返回有多少种 decode ways。

Mapping:

A = 1
B = 2
...
Z = 26

Example:

s = "226"
answer = 3

Ways:

2 6  → B B F
6   → V F
26   → B Z

State Definition

dp[i] = decode prefix s[0:i] 的 ways 数量

Recurrence

对于位置 i：

Single digit

如果：

s[i - 1] != "0"

那么：

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

Two digits

如果：

10 <= int(s[i - 2:i]) <= 26

那么：

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

Code

def num_decodings(s):
    if not s:
        return 0

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

    dp[0] = 1
    dp[1] = 1 if s[0] != "0" else 0

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

        if one != "0":
            dp[i] += dp[i - 1]

        if 10 <= int(two) <= 26:
            dp[i] += dp[i - 2]

    return dp[n]

👉 面试回答

对 Decode Ways，我定义 dp[i] 为 prefix s[0:i] 的 decode ways。

在每个位置，我检查最后一位是否能单独 decode，以及最后两位是否能 decode。

所有 valid transition 的 ways 加起来，就是 dp[i]。

1️⃣3️⃣ Min Cost Climbing Stairs

Problem

每次可以爬一阶或两阶。每个 step 有 cost。返回到达 top 的 minimum cost。

State Definition

dp[i] = 到达 step i 的 minimum cost

Top 是：

step n

Recurrence

到达 step i 可以来自：

i - 1
or
i - 2

所以：

dp[i] = min(
    dp[i - 1] + cost[i - 1],
    dp[i - 2] + cost[i - 2]
)

Code

def min_cost_climbing_stairs(cost):
    n = len(cost)

    dp = [0] * (n + 1)

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

    return dp[n]

👉 面试回答

对 Min Cost Climbing Stairs，我定义 dp[i] 为到达 step i 的 minimum cost。

Top 可以看成 step n。

到达 step i 可以从 i - 1 或 i - 2 来。

需要支付的是离开的那个 step 的 cost。

所以 recurrence 是两种来源取 min。

1️⃣4️⃣ House Robber as Sequence DP

Problem

一排 houses，不能 rob 相邻 houses。

State Definition

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

Recurrence

对于 house i：

skip i:
    dp[i - 1]

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

所以：

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]

    prev2 = nums[0]
    prev1 = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current

    return prev1

👉 面试回答

House Robber 是 choose-or-skip 的 sequence DP。

对每个 house，我可以 skip 它，保留 previous best；或者 rob 它，并加上 two houses before 的 best。

因为只依赖 previous two states，所以可以优化到 O(1) space。

1️⃣5️⃣ Jump Game

Problem

每个 element 表示 maximum jump length，判断能否到达 last index。

DP State

dp[i] = index i 是否 reachable

DP Code

def can_jump_dp(nums):
    n = len(nums)
    dp = [False] * n
    dp[0] = True

    for i in range(n):
        if not dp[i]:
            continue

        furthest = min(n - 1, i + nums[i])

        for j in range(i + 1, furthest + 1):
            dp[j] = True

    return dp[-1]

Greedy Note

这个问题有更好的 greedy solution。

def can_jump(nums):
    farthest = 0

    for i, jump in enumerate(nums):
        if i > farthest:
            return False

        farthest = max(farthest, i + jump)

    return True

👉 面试回答

Jump Game 可以用 DP 建模， dp[i] 表示 index i 是否 reachable。

但这个题有更好的 greedy solution。

我维护当前能到达的 farthest index。

如果某个 i 超过 farthest，说明无法到达。

否则持续更新 farthest。

1️⃣6️⃣ Paint House

Problem

有一排 houses 和若干 colors。每个 house 涂不同 color 有不同 cost。相邻 houses 不能同 color。返回 minimum total cost。

State Definition

dp[i][color] = 涂完 house 0 到 i，且 house i 使用 color 的 minimum cost

Recurrence

对于 3 colors：

dp[i][0] = cost[i][0] + min(dp[i - 1][1], dp[i - 1][2])
dp[i][1] = cost[i][1] + min(dp[i - 1][0], dp[i - 1][2])
dp[i][2] = cost[i][2] + min(dp[i - 1][0], dp[i - 1][1])

Code

def min_cost(costs):
    if not costs:
        return 0

    dp = [row[:] for row in costs]

    for i in range(1, len(costs)):
        dp[i][0] += min(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] += min(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] += min(dp[i - 1][0], dp[i - 1][1])

    return min(dp[-1])

👉 面试回答

对 Paint House，我定义 dp[i][color] 为涂完前 i 个 houses，并且 house i 使用某个 color 时的 minimum cost。

因为相邻 house 不能同 color，所以前一个 house 必须使用不同 color。

最终答案是最后一行中的最小值。

1️⃣7️⃣ Arithmetic Slices

Problem

统计长度至少为 3 的 arithmetic subarrays。

Arithmetic subarray 要求 consecutive differences 相同。

State Definition

dp[i] = 以 index i 结尾的 arithmetic slices 数量

Recurrence

如果：

nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]

那么：

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

否则：

dp[i] = 0

Code

def number_of_arithmetic_slices(nums):
    n = len(nums)

    if n < 3:
        return 0

    dp = [0] * n
    total = 0

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

        total += dp[i]

    return total

👉 面试回答

对 Arithmetic Slices，我定义 dp[i] 为以 index i 结尾的 arithmetic subarrays 数量。

如果最后三个数保持相同 difference，那么所有以 i - 1 结尾的 arithmetic slices 都可以延伸到 i，另外还会新增一个长度为 3 的 slice。

所以 dp[i] = dp[i - 1] + 1。

1️⃣8️⃣ Longest Alternating Subsequence

Problem

找 longest subsequence，要求相邻 differences 在 positive 和 negative 之间交替。

State Definition

使用两个 states：

up[i] = 以 i 结尾，最后一次 movement 是 upward 的 longest alternating subsequence
down[i] = 以 i 结尾，最后一次 movement 是 downward 的 longest alternating subsequence

Space Optimized Code

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

    up = 1
    down = 1

    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            up = down + 1
        elif nums[i] < nums[i - 1]:
            down = up + 1

    return max(up, down)

👉 面试回答

对 alternating sequence 问题，我通常使用两个 DP states。

一个 state 表示最后 movement 是 upward。

另一个 state 表示最后 movement 是 downward。

当当前 difference 是 positive，它可以延续之前的 down state。

当当前 difference 是 negative，它可以延续之前的 up state。

1️⃣9️⃣ State Choice: Prefix vs Ending

Prefix State

当问题满足这些特征时使用 prefix state：

问题问 prefix 是否可以形成
答案来自 split point
当前位置代表 length

Examples:

Word Break
Decode Ways
Min Cost Climbing Stairs

Ending State

当问题满足这些特征时使用 ending state：

solution 必须包含 current index
需要 best sequence ending here
需要比较 current element 和 previous elements

Examples:

Maximum Subarray
LIS
Arithmetic Slices
LCIS

👉 面试回答

Sequence DP 中一个关键选择是： state 是 prefix-based，还是 ending-at-index。

Prefix-based state 适合构造或验证 prefixes。

Ending-at-index state 适合 current element 必须参与当前 subproblem 的问题。

这个选择通常决定 recurrence。

2️⃣0️⃣ Complexity Analysis

Common Formula

对于 sequence DP：

Time = number of states × transition cost

Examples

Maximum Subarray:

states = n
transition = O(1)
time = O(n)

LIS basic DP:

states = n
transition = O(n)
time = O(n²)

Word Break:

states = n
transition = O(n) split points
time = O(n²) plus substring cost

Space Complexity

通常是：

O(n)

如果只需要 previous few states：

O(1)

👉 面试回答

Sequence DP 的复杂度可以用： states 数量乘以 transition cost 来分析。

如果每个 state 只依赖常数个 previous states，通常是 O(n)。

如果每个 state 都要扫描所有 previous positions，通常是 O(n²)。

如果只需要少数 previous states， space 可以优化。

2️⃣1️⃣ 常见 Edge Cases

Empty Input

nums = []
s = ""

Single Element

nums = [x]

All Negative Numbers

Maximum Subarray 中很重要。

答案应该是最大的 negative number，不是 0。

Leading Zero

Decode Ways 中很重要。

"06" is invalid

Duplicate Values

LIS 中很重要。

Strictly increasing 意味着：

nums[j] < nums[i]

不是：

nums[j] <= nums[i]

Prefix Empty State

String DP 中：

dp[0]

通常表示 empty prefix。

👉 面试回答

Sequence DP 常见 edge cases 包括 empty input、 single element、 all negative numbers、 decode ways 中的 leading zero、 LIS 中的 duplicate values，以及 string DP 中 dp[0] 的含义。

我通常会先测试最小输入。

2️⃣2️⃣ 常见错误

Mistake 1: dp[i] 含义不清楚

混淆：

dp[i] = ending at i 的答案

和：

dp[i] = first i elements 的答案

Mistake 2: Base Case 错误

例如：

dp[0] for empty prefix
dp[0] for first element

这两个含义完全不同。

Mistake 3: 忘记 Global Answer

对于 ending-at-index DP，答案通常是：

max(dp)

不一定是：

dp[-1]

Examples:

Maximum Subarray
LIS

Mistake 4: Strict vs Non-Strict Comparison

LIS:

nums[j] < nums[i]

Non-decreasing subsequence:

nums[j] <= nums[i]

Mistake 5: 不安全的 Space Optimization

只有在确认 dependencies 后才能 optimize space。

👉 面试回答

Sequence DP 常见错误包括： state meaning 不清楚、 base case 错误、 ending-at-index DP 中错误返回 dp[-1]、 strict comparison 处理错误、以及没有理解 dependencies 就优化 space。

我会先用自然语言定义 dp[i]。

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

Good Fit

当问题满足：

input is ordered
current answer depends on previous positions
problem asks for longest, maximum, minimum, count, or feasibility
subproblem can be defined by index
prefix or ending-at-index recurrence exists

Problem Signals

看到这些关键词想到 sequence DP：

longest
maximum subarray
ways to decode
can be segmented
ending at
prefix
subsequence
subarray
minimum cost
choose or skip in a line

👉 面试回答

当 input 有顺序，并且 current answer 依赖 earlier positions 时，我会考虑 sequence DP。

常见信号包括 longest subsequence、maximum subarray、 decode ways、string segmentation、sequence 上的 minimum cost，或者 line 上的 choose-or-skip decision。

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

Not Good Fit

Sequence DP 不适合：

there is no useful order
need shortest path in a graph
need all solutions explicitly
need range query updates
local greedy choice is sufficient

Better Alternatives

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

👉 面试回答

Sequence DP 适合 index order 有意义的问题。

如果问题本质是 graph shortest path， BFS 或 Dijkstra 更合适。

如果题目要求所有 solutions， backtracking 更合适。

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

2️⃣5️⃣ 标准模板

Ending-at-Index Template

def sequence_dp_ending(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if can_extend(nums[j], nums[i]):
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Prefix DP Template

def sequence_dp_prefix(s):
    n = len(s)
    dp = [False] * (n + 1)

    dp[0] = True

    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and valid(s[j:i]):
                dp[i] = True
                break

    return dp[n]

Kadane Template

def kadane(nums):
    current = nums[0]
    best = nums[0]

    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)

    return best

Decode Ways Template

def decode_ways(s):
    n = len(s)
    dp = [0] * (n + 1)

    dp[0] = 1
    dp[1] = 1 if s[0] != "0" else 0

    for i in range(2, n + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]

        if 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]

    return dp[n]

Choose-or-Skip Sequence Template

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

    prev2 = 0
    prev1 = 0

    for num in nums:
        current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current

    return prev1

🧠 Staff-Level Answer Final

👉 面试回答完整版本

Sequence DP 用于 input 有顺序的场景，比如 array 或 string，并且当前位置的答案依赖 previous positions。

第一个问题是： dp[i] 到底表示什么？

Sequence DP 中有两种常见 state definition。

第一种是 prefix-style： dp[i] 表示使用前 i 个元素的答案，或者 prefix s[0:i] 的答案。这常见于 Word Break、Decode Ways、Min Cost Climbing Stairs。

第二种是 ending-at-index style： dp[i] 表示必须以 index i 结尾的最佳答案。这常见于 Maximum Subarray、Longest Increasing Subsequence、 Longest Continuous Increasing Subsequence 和 Arithmetic Slices。

这个区别非常重要，因为它决定 recurrence 和 final answer。

对 Maximum Subarray， dp[i] 是以 i 结尾的 best subarray sum。每个 index 上，要么从当前元素开始新的 subarray，要么延续之前的 subarray。最终答案是所有 dp[i] 的最大值。

对 LIS， dp[i] 是以 i 结尾的 longest increasing subsequence。我检查所有 previous positions j。如果 nums[j] 小于 nums[i]，就可以用 nums[i] 延续 dp[j]。

对 Word Break， dp[i] 表示 s[0:i] 是否可以被 segment。我尝试所有 split point j。如果 dp[j] 是 true，且 s[j:i] 是 dictionary word，那么 dp[i] 是 true。

对 Decode Ways， dp[i] 表示 prefix s[0:i] 的 decode ways。在每个位置，我检查最后一位和最后两位是否能形成 valid letter。

常见复杂度分析方式是： states 数量 × transition cost。如果每个 state 只依赖前一个 state，通常是 O(n)。如果每个 state 都扫描所有 previous positions，通常是 O(n²)。

当 recurrence 只依赖少量 previous states 时，可以进行 space optimization。

高级工程师解释 sequence DP 时，我会讲清楚： state 是 prefix-based 还是 ending-at-index， dp[i] 的含义是什么， current element 如何延续 previous states， final answer 是 dp[n] 还是 max(dp)， base cases 是什么，以及是否需要 strict 或 non-strict comparison。

⭐ Final Insight

Sequence DP 的核心不是“写一个 dp array”。

它的核心是利用 input order，把 current position 和 previous positions 建立关系。

Senior-level 的重点是：

dp[i] 是 prefix answer 还是 ending-at-index answer， current element 是否必须被包含， recurrence 从哪些 previous states 来， final answer 是 dp[n] 还是 max(dp)， base case 如何定义，以及能不能安全地 optimize space。

能讲清楚这些， Sequence DP 就是一类处理 array/string order、subarray、subsequence 和 prefix decisions 的核心 DP 模型。