一维 DP · DP 1D

一句话骨架：定义 dp[i] =「以 i 结尾 / 到达 i 时」的某个最优值，写出转移方程与初始值——能不能滚动数组优化空间是面试加分项。

解题四步

1. 状态定义：dp[i] 表示「以 i 结尾」/「前 i 个」的什么？
2. 转移方程：dp[i] = f(dp[i-1], dp[i-2], ...) 怎么推？
3. 初始值与边界：dp[0]、dp[1] 如何初始化，循环从哪开始？
4. 空间优化：只依赖前 1-2 个状态时用变量代替数组。

通用模板

# 经典「只依赖前两个」的滚动写法
prev2, prev1 = base0, base1
for i in range(start, n):
    cur = transition(prev1, prev2, nums[i])  # 转移方程
    prev2, prev1 = prev1, cur  # 同行赋值,避免覆盖
return prev1

关卡 1 · 爬楼梯

学习目标

掌握「加法原理 → 二阶递推 → 斐波那契」的链路，理解为什么 dp[0]=1（而非 0）才让转移自洽。

#70爬楼梯简单

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1

输入n = 2

输出2

💡 1+1 / 2

示例 2

输入n = 3

输出3

💡 1+1+1 / 1+2 / 2+1

示例 3

输入n = 5

输出8

💡 斐波那契数列：1,2,3,5,8

约束

• 1 ≤ n ≤ 45

💡 思路：到达第 i 阶要么从 i-1 阶迈 1 步上来、要么从 i-2 阶迈 2 步上来，方案数互不相交，所以 dp[i] = dp[i-1] + dp[i-2]——这就是斐波那契。只依赖前两个状态，可以用两个滚动变量把空间压到 O(1)。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def climbStairs(n: int) -> int: 2    if n <= 2: 3        return n 4    # dp[i] 表示「到达第 i 阶」的方法数 5    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2 6    for i in range(3, n + 1): 7        cur = prev1 + prev2 8        prev2, prev1 = prev1, cur 9    return prev1

🐞 单步可视化

示例：n = 12

代码L2

 1def climbStairs(n: int) -> int: 2    if n <= 2: 3        return n 4    # dp[i] 表示「到达第 i 阶」的方法数 5    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2 6    for i in range(3, n + 1): 7        cur = prev1 + prev2 8        prev2, prev1 = prev1, cur 9    return prev1

数据流

n12prev21prev12

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

i=9

i=10

i=11

i=12

dp

·

·

·

·

·

·

·

·

·

·

·

·

1 / 34检查 n=12，n>2 进入 DP 路径

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

dp[i] 最自然的状态定义是？

转移方程应当是？

 1def climbStairs(n: int) -> int: 2    if n <= 2: 3        return n 4    # dp[i] 表示「到达第 i 阶」的方法数 5    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2 6    for i in range(3, n + 1): 7        cur = prev1 + prev2 8        prev2, prev1 = prev1, cur 9    return prev1

若以 dp[i] = 到达第 i 阶的方法数定义状态，初始值最稳的写法是？

为什么不能把 dp[0] 设为 0？

此题与斐波那契数列的关系？

空间优化的核心观察是？

 1def climbStairs(n: int) -> int: 2    if n <= 2: 3        return n 4    # dp[i] 表示「到达第 i 阶」的方法数 5    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2 6    for i in range(3, n + 1): 7        cur = prev1 + prev2 8        prev2, prev1 = prev1, cur 9    return prev1

滚动更新 prev2, prev1 = prev1, cur 这种 Python 同行赋值的关键是？

 1def climbStairs(n: int) -> int: 2    if n <= 2: 3        return n 4    # dp[i] 表示「到达第 i 阶」的方法数 5    prev2, prev1 = 1, 2  # dp[1]=1, dp[2]=2 6    for i in range(3, n + 1): 7        cur = prev1 + prev2 8        prev2, prev1 = prev1, cur 9    return prev1

若不做空间优化、用一维 dp 数组，下面循环范围正确的是？

时间复杂度是？

空间复杂度（用滚动变量版）是？

若题目变成"每次能爬 1, 2, 或 3 阶"，转移方程会变成？

关于"为什么用 DP 而不是直接递归"，最准确的说法是？

关卡 2 · 打家劫舍

学习目标

学会"相邻互斥型"DP：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 的两支转移分别对应"不偷 / 偷"——这套模板可推广到环形（213）、二叉树版（337）。

#198打家劫舍中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1

输入nums = [1,2,3,1]

输出4

💡 偷 nums[0]=1 + nums[2]=3 = 4

示例 2

输入nums = [2,7,9,3,1]

输出12

💡 偷 nums[0]+nums[2]+nums[4] = 2+9+1 = 12

示例 3

输入nums = [2,1,1,2]

输出4

💡 偷 nums[0]+nums[3] = 2+2 = 4

约束

• 1 ≤ nums.length ≤ 100
• 0 ≤ nums[i] ≤ 400

💡 思路：到第 i 间房有两种选择：① 不偷它 → 收益 = dp[i-1]；② 偷它 → 必须放弃 i-1，收益 = dp[i-2] + nums[i]。两者取大。这是「相邻互斥型」DP 的母题。

✅ 完整解法

时间 O(n) · 空间 O(1)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def rob(nums: list[int]) -> int: 2    if not nums: 3        return 0 4    n = len(nums) 5    if n == 1: 6        return nums[0] 7    # dp[i] = 偷到第 i 间为止能拿到的最大金额（i 偷不偷都行） 8    prev2, prev1 = nums[0], max(nums[0], nums[1]) 9    for i in range(2, n):10        cur = max(prev1, prev2 + nums[i])11        prev2, prev1 = prev1, cur12    return prev1

🐞 单步可视化

示例：nums = [2, 7, 9, 3, 1]

代码L2

 1def rob(nums: list[int]) -> int: 2    if not nums: 3        return 0 4    n = len(nums) 5    if n == 1: 6        return nums[0] 7    # dp[i] = 偷到第 i 间为止能拿到的最大金额（i 偷不偷都行） 8    prev2, prev1 = nums[0], max(nums[0], nums[1]) 9    for i in range(2, n):10        cur = max(prev1, prev2 + nums[i])11        prev2, prev1 = prev1, cur12    return prev1

数据流

prev22prev17

i=0

i=1

i=2

i=3

i=4

dp

2

7

·

·

·

1 / 12检查输入非空

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

dp[i] 的状态定义最准确的是？

转移方程的两支分别表示什么？

 1def rob(nums: list[int]) -> int: 2    if not nums: 3        return 0 4    n = len(nums) 5    if n == 1: 6        return nums[0] 7    # dp[i] = 偷到第 i 间为止能拿到的最大金额（i 偷不偷都行） 8    prev2, prev1 = nums[0], max(nums[0], nums[1]) 9    for i in range(2, n):10        cur = max(prev1, prev2 + nums[i])11        prev2, prev1 = prev1, cur12    return prev1

初始值 dp[0] = nums[0]、dp[1] = max(nums[0], nums[1]) 这样写的理由？

 1def rob(nums: list[int]) -> int: 2    if not nums: 3        return 0 4    n = len(nums) 5    if n == 1: 6        return nums[0] 7    # dp[i] = 偷到第 i 间为止能拿到的最大金额（i 偷不偷都行） 8    prev2, prev1 = nums[0], max(nums[0], nums[1]) 9    for i in range(2, n):10        cur = max(prev1, prev2 + nums[i])11        prev2, prev1 = prev1, cur12    return prev1

若把 dp[1] = max(nums[0], nums[1]) 错写成 dp[1] = nums[1]，会出什么问题？

prev2, prev1 = prev1, cur 在 Python 里能正确滚动的原因？

 1def rob(nums: list[int]) -> int: 2    if not nums: 3        return 0 4    n = len(nums) 5    if n == 1: 6        return nums[0] 7    # dp[i] = 偷到第 i 间为止能拿到的最大金额（i 偷不偷都行） 8    prev2, prev1 = nums[0], max(nums[0], nums[1]) 9    for i in range(2, n):10        cur = max(prev1, prev2 + nums[i])11        prev2, prev1 = prev1, cur12    return prev1

若 nums 全是 0，max(prev1, prev2 + nums[i]) 还正确吗？

为什么不能用贪心"每次偷最大值"？

此题的"环形版"（LeetCode 213，首尾相接）正确思路是？

时间复杂度是？

空间复杂度（滚动变量版）是？

若 nums 含负数（题目变体，允许"罚钱"），上面代码哪一步可能错？

若把状态扩展为 dp[i][0/1]（0=不偷 i, 1=偷 i），转移应是？

关卡 3 · 最长递增子序列

学习目标

区分朴素 O(n²) 的「以 i 结尾」状态与 O(n log n) 贪心 + 二分中 tails[k] 的"长度档位末尾最小值"语义；理清 bisect_left vs bisect_right 在严格/非严格递增时的取舍。

#300最长递增子序列中等

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

请你设计时间复杂度为 O(n log(n)) 的算法解决此问题。

示例 1

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

输出4

💡 LIS 为 [2,3,7,101] 或 [2,3,7,18]

示例 2

输入nums = [0,1,0,3,2,3]

输出4

示例 3

输入nums = [7,7,7,7,7,7,7]

输出1

💡 严格递增——重复元素只能选一次

约束

• 1 ≤ nums.length ≤ 2500
• -10⁴ ≤ nums[i] ≤ 10⁴

💡 思路：两套思路：① 朴素 DP O(n²)：dp[i] = 以 nums[i] 结尾的 LIS 长度，dp[i] = max(dp[j])+1 (j<i, nums[j]<nums[i])。② 贪心 + 二分 O(n log n)：维护 tails，tails[k] 是「长度 k+1 的 LIS 当前可能的最小末尾」。每来一个数二分找到它该替换的位置；若大于所有末尾就 append。注意 tails 本身**不一定是某条真实 LIS**，但它的长度等于 LIS 长度。

✅ 完整解法

时间 O(n log n) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

🐞 单步可视化

示例：nums = [10, 9, 2, 5, 3, 7, 101, 18]（O(n²) DP 解法）

代码L5

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

数据流

n8

10

9

2

5

3

7

101

18

dp

·

·

·

·

·

·

·

·

1 / 55初始化 dp 数组全为 1（每个元素自身就是长度 1 的 LIS）

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

朴素 O(n²) 版本中，dp[i] 最自然的状态定义是？

朴素 O(n²) 转移方程是？

O(n log n) 版本中 tails 数组的语义是？

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

为什么 tails 始终是严格递增的？

严格递增 LIS 应当用 bisect_left 还是 bisect_right？

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

若题目改为"非严格"递增（允许等值），二分函数应改为？

if idx == len(tails): tails.append(x) 这个分支何时触发？

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

tails[idx] = x 这一步的意义是？

 1from bisect import bisect_left 2  3def lengthOfLIS(nums: list[int]) -> int: 4    # tails[k] 表示「长度为 k+1 的递增子序列」当前可能的末尾最小值 5    tails: list[int] = [] 6    for x in nums: 7        # 严格递增 → bisect_left；如果允许「非严格」改用 bisect_right 8        idx = bisect_left(tails, x) 9        if idx == len(tails):10            tails.append(x)  # x 比所有末尾都大,延长 LIS11        else:12            tails[idx] = x  # 把长度为 idx+1 的「末尾候选」收紧13    return len(tails)

为什么 O(n log n) 版本的 tails 不一定就是某条真实 LIS？

bisect_left(tails, x) 的复杂度是？

能否用堆 / 平衡 BST 替代 bisect？

空间复杂度是？

关于"两种解法的取舍"，最准确的说法是？

关卡 4 · 单词拆分

学习目标

建立「前缀 DP」：dp[i] = s[:i] 是否可拆。学会用 set 把字典查询压到 O(1)，并用「最长单词长度」剪枝内层循环。

#139单词拆分中等

♥♥♥♥♥+0 XP🔥 0

0 / 13

📝 题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1

输入s = "leetcode", wordDict = ["leet","code"]

输出true

💡 "leet" + "code"

示例 2

输入s = "applepenapple", wordDict = ["apple","pen"]

输出true

💡 可以重复使用 apple

示例 3

输入s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

输出false

约束

• 1 ≤ s.length ≤ 300
• 1 ≤ wordDict.length ≤ 1000
• 1 ≤ wordDict[i].length ≤ 20
• wordDict 内单词互不相同

💡 思路：`dp[i]` = s[:i] 是否可拆。要让 dp[i]=True，存在某个 j (0≤j<i) 使得 dp[j]=True 且 s[j:i] 在字典中——即「前 j 个可拆 + 后缀 s[j:i] 是单词」。把 wordDict 转成 set 让查询变 O(1)；再用「最长单词长度」剪枝，避免无效内层。

✅ 完整解法

时间 O(n · L) · 空间 O(n)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

🐞 单步可视化

示例：s = "leetcode", wordDict = ["leet", "code"]

代码L2

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

数据流

s"leetcode"dict["leet","code"]maxLen4

i=0

i=1

i=2

i=3

i=4

i=5

i=6

i=7

i=8

dp

·

·

·

·

·

·

·

·

·

1 / 40把 wordDict 转 set 加速查询，maxLen = 4

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

dp[i] 最准确的状态定义是？

边界 dp[0] = True 的含义？

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

为什么把 wordDict 转成 set？

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

内层循环 for j in range(0, i) 的语义是？

判断条件 dp[j] and s[j:i] in word_set 的两部分顺序能不能交换？

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

dp[i] 一旦置 True 后立即 break 的好处？

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

剪枝 range(max(0, i - max_len), i) 的依据是？

 1def wordBreak(s: str, wordDict: list[str]) -> bool: 2    word_set = set(wordDict)  # O(1) 查询 3    max_len = max((len(w) for w in word_set), default=0) 4    n = len(s) 5    # dp[i] 表示 s[:i] 是否可被拆分;dp[0] = True 是「空串」边界 6    dp = [False] * (n + 1) 7    dp[0] = True 8    for i in range(1, n + 1): 9        # 只看最近 max_len 个起点 j 即可——再往左 s[j:i] 不可能在字典里10        for j in range(max(0, i - max_len), i):11            if dp[j] and s[j:i] in word_set:12                dp[i] = True13                break14    return dp[n]

s[j:i] 在 Python 里的复杂度是？

若不剪枝（内层 j 从 0 到 i-1），最坏时间复杂度是？

为什么不能用贪心"从左到右每次切下最长可识别前缀"？

记忆化递归（DFS+cache）和本 DP 的关系是？

空间复杂度是？

若题目改成 "返回所有可能的拆分方案"（LC 140），代码主体应改为？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
279	完全平方数	中等	dp[i] = min(dp[i-k²]) + 1，对每个 i 枚举可减的平方数
322	零钱兑换	中等	dp[i] = min(dp[i-c]) + 1，无解返回 -1（注意初始化为 inf）
118	杨辉三角	简单	一维生成第 i 行 = 上一行错位相加
152	乘积最大子数组	中等	双 dp：同时维护以 i 结尾的 max 与 min（负负得正）
32	最长有效括号	困难	栈记录左括号下标 / 或 dp[i] 表示以 i 结尾的有效长度
121	买卖股票的最佳时机	简单	边扫边维护 min_price 与 max_profit，本质是 dp
55	跳跃游戏	中等	贪心维护 max_reach，可视作 dp[i] 是否可达的常数空间版
45	跳跃游戏 II	中等	贪心 BFS 思想分层扩展，O(n) 跳跃次数

面试常踩

1. dp[0] 选 0 还是 1——取决于状态定义。爬楼梯里 dp[0]=1（"空走法"算一种）才能让 dp[2]=dp[1]+dp[0]=2 自洽。
2. 滚动赋值方向——Python 同行赋值 prev2, prev1 = prev1, cur 是右侧元组先求值再解包，避免顺序敏感。
3. bisect_left vs bisect_right——严格递增 LIS 用 bisect_left（等值时替换），非严格用 bisect_right（等值时延长）。这是一字之差导致 WA 的经典坑。
4. DP 不是贪心——单词拆分、打家劫舍等都不能"每次选最大/最长"，必须枚举切割点 / 决策点。