🧩 01-数据结构与算法 · 主题 8:动态规划(重头戏)¶
DP 是秋招算法第一重点:考察「把大问题分解为重叠子问题 + 最优子结构」的建模能力。 本 notebook 目标:吃透四步法 → 掌握背包/LIS/LCS/编辑距离/区间/股票六大模板 → 通过 25 道自测。
前置:主题 7(递归)。运行环境:Python 3.8+,无第三方依赖。
核心概念¶
(a) 🗂️ 动态规划:四步法 + 六大经典模板¶
DP 是秋招算法第一重点:考察"把大问题分解为重叠子问题 + 最优子结构"的建模能力。本 notebook 吃透四步法,掌握背包/LIS/LCS/编辑距离/区间/股票六大模板。
flowchart TB
N1["🧩 DP 四步法"] --> N2["一维 DP:70 / 198 / 53 / 121"]
N2 --> N3["01 背包:容量必须逆序"]
N3 --> N4["完全背包:容量正序"]
N1 --> N5["最长类:LIS / LCS / 回文"]
N1 --> N6["编辑距离 72:填表推导"]
N5 --> N7["区间 DP 与股票状态机"]
N6 --> N8["路径类 62/64 与记忆化搜索"]
N8 --> N9["常见坑与复杂度模板"]
- N1 · DP 四步法:写任何 DP 前先走四步:① 判断能不能拆(重叠子问题 + 最优子结构)→ ② 定义 dp[i] 的含义 → ③ 写状态转移方程 → ④ 定边界与遍历顺序。四步想清楚再写代码。
- N2 · 一维 DP:爬楼梯(斐波那契)、打家劫舍(偷不偷当前)、最大子数组和(Kadane)、买卖股票一次(记录最低价)——四道入门题建立一维 DP 感觉。
- N3 · 01 背包:每件物品只取一次:二维转一维滚动数组后,容量必须逆序遍历,否则一件物品会被"重复选"——这是面试白板必讲点。
- N4 · 完全背包:每件可无限取:容量正序遍历即可;416 分割等和子集、518 零钱兑换 II 分别是它的判定/计数变形。
- N5 · 最长类:LIS(子序列递增)、LCS(两串公共子序列)、最长回文子串(区间扩展)——最长类都带"选/不选当前字符"的味道,一套转移思想复用三题。
- N6 · 编辑距离 72:最经典的填表推导:dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符要几步,增/删/替三种操作取最小,必背推导。
- N7 · 区间 DP 与股票状态机:区间 DP(最长回文子序列)用"小区间推大区间";股票系列统一成状态机——天数 × 是否持股 × 交易次数,一类题全通。
- N8 · 路径类与记忆化搜索:路径类(不同路径/最小路径和)逐格累加即可;记忆化搜索是自顶向下 DP(递归 + 缓存),与自底向上殊途同归。
- N9 · 常见坑与复杂度模板:dp 含义定义错、初始化出错、遍历顺序反(尤其背包)、压缩空间后的边界——结尾附复杂度回答模板与自测清单。
📷 0-1 背包:在容量约束下选物品使价值最大(DP 二维→一维滚动) 图源:Wikimedia Commons(开放授权)
§1 四步法(写任何 DP 前先默写)¶
判断 DP 的两把尺子¶
- 最优子结构:全局最优可由子问题最优组合而成(贪心不满足时才想到 DP)
- 重叠子问题:不同路径会反复计算同一个子问题(递归爆搜会重复)
反例:最长简单路径无最优子结构(不可分);贪心可解的题强用 DP 是杀鸡用牛刀。
四步法¶
- 定义状态 $dp[i]$:$i$ 的含义(下标/容量/长度)+ $dp[i]$ 存什么(最大值/方案数/布尔)
- 转移方程:$dp[i]$ 从哪些更小的状态推来
- 初始化:边界($dp[0]$、$dp[1]$、空串/空背包)
- 遍历顺序:一维从前往后 / 从后往前(背包逆序);二维行主序 / 按区间长度
两类实现¶
- 自底向上(递推):for 循环填表,面试默认写法,省递归栈
- 自顶向下(记忆化搜索):递归 + memo 字典/数组,思路直白、无需考虑遍历顺序
$$\text{记忆化} \iff \text{递推} \quad (\text{时间复杂度相同,空间记忆化多递归栈})$$
§2 一维 DP:爬楼梯 / 打家劫舍 / 最大子数组和¶
70 爬楼梯¶
一次爬 1 或 2 阶:
$$dp[i] = dp[i-1] + dp[i-2], \quad dp[1]=1,\ dp[2]=2$$
滚动变量优化空间 $O(1)$(只保留前两个)。
198 打家劫舍(不可取相邻)¶
$$dp[i] = \max(dp[i-1],\ dp[i-2] + nums[i])$$
- 不偷 $i$:继承 $dp[i-1]$;偷 $i$:$dp[i-2] + nums[i]$
53 最大子数组和(Kadane)¶
$$dp[i] = \max(nums[i],\ dp[i-1] + nums[i])$$
要么新开一段(nums[i]),要么接续前一段。
121 买卖股票的最佳时机(只能买卖一次)¶
$$dp[i] = \max(dp[i-1],\ nums[i] - \min_{j<i} nums[j])$$
等价于维护历史最低价,一趟遍历。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ============== 一维 DP 四题:70 / 198 / 53 / 121 ==============
# 【题目目标】① 70 爬楼梯(一次爬 1/2 阶的方案数);② 198 打家劫舍(不能偷相邻
# 两家,求最大收益);③ 53 最大子数组和(Kadane);④ 121 买卖股票一次
# 【算法思路】70:dp[i]=dp[i-1]+dp[i-2],用两个滚动变量压到 O(1) 空间;
# 198:dp[i]=max(dp[i-1], dp[i-2]+nums[i]),滚动 prev2/prev1;
# 53:cur=max(x, cur+x)(新开一段 or 接续),best 记全局最优;
# 121:每次更新历史最低价 min_price,用 p-min_price 尝试卖出
# 【变量含义】a/b:爬楼梯的滚动变量(dp[1]、dp[2]);prev2/prev1:打家劫舍中
# 上上家/上一家收益;cur/best:最大子数组的当前段和/全局最优;
# min_price:股票历史最低价;best:最大利润
# 【循环不变量】滚动变量始终保存最近两个(或一个)子问题的答案,遍历完即为结果
# 【递归终止】无递归,循环天然结束;递推边界:爬楼梯 dp[1]=1、dp[2]=2;
# 打家劫舍空数组收益 0;Kadane 从 nums[0] 起步
# 【关键边界】爬楼梯 n=1 时应返回 a;打家劫舍循环从空收益 0 开始;Kadane 全负
# 数时仍能选出最大(从 nums[0] 初始化,不用 0);股票价格单调下跌时
# 利润保持 0(不买不卖)
# 【复杂度】四题均为 O(n) 时间、O(1) 空间
# 70. 爬楼梯:dp[i]=dp[i-1]+dp[i-2],用两个滚动变量把空间压到 O(1)
def climb_stairs(n):
a, b = 1, 2 # dp[1], dp[2]
for _ in range(3, n + 1): # 从第 3 阶开始递推
a, b = b, a + b # 滚动更新:b 变为下一阶的 dp 值
return b if n >= 2 else a # n>=2 时取 b(即 dp[n]),n=1 时取 a
# 198. 打家劫舍:不能偷相邻两家,dp[i]=max(dp[i-1], dp[i-2]+nums[i])
# 滚动变量:prev2 是上上家的结果,prev1 是上一家的结果
def rob(nums):
prev2, prev1 = 0, 0 # 初始:没有房子可偷时收益为 0
for x in nums: # 遍历每个元素
cur = max(prev1, prev2 + x) # 不偷 vs 偷当前
prev2, prev1 = prev1, cur # 滚动推进:新上上家 = 旧上家
return prev1 # 遍历完所有房子后的最大收益
# 53. 最大子数组和(Kadane):要么新开一段,要么把当前元素接在前一段后面
def max_sub_array(nums):
best = cur = nums[0] # 当前子段和 cur 与全局最优 best 都从第一个元素开始
for x in nums[1:]: # 从第二个元素开始遍历
cur = max(x, cur + x) # 新开一段 vs 接续
best = max(best, cur) # 更新全局最优
return best # 返回最优答案
# 121. 买卖股票的最佳时机:只买卖一次,维护历史最低价,每天尝试卖出
def max_profit(prices):
min_price = float('inf') # 历史最低价,初始设为无穷大
best = 0 # 最大利润,初始为 0
for p in prices: # 遍历每个交易日的价格
min_price = min(min_price, p) # 更新历史最低价
best = max(best, p - min_price) # 今天以最低价买入再卖出,更新最大利润
return best # 返回最优答案
print('climb(5) =', climb_stairs(5)) # 期望 8
print('rob([2,7,9,3,1]) =', rob([2, 7, 9, 3, 1])) # 期望 12(2+9+1)
print('rob([2,1,1,2]) =', rob([2, 1, 1, 2])) # 期望 4(2+2)
print('max_sub_array([-2,1,-3,4,-1,2,1,-5,4]) =', max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print('max_profit([7,1,5,3,6,4]) =', max_profit([7, 1, 5, 3, 6, 4])) # 期望 5
climb(5) = 8 rob([2,7,9,3,1]) = 12 rob([2,1,1,2]) = 4 max_sub_array([-2,1,-3,4,-1,2,1,-5,4]) = 6 max_profit([7,1,5,3,6,4]) = 5
§3 背包问题(面试手撕重灾区)¶
01 背包(每件只取一次)¶
容量 $W$、物品 $i$ 重 $w_i$ 值 $v_i$:
$$dp[j] = \max(dp[j],\ dp[j - w_i] + v_i), \quad j \text{ 从大到小遍历}$$
为什么容量逆序遍历:正序会让同一物品被重复取(dp[j-w] 已经是更新后的值)。
滚动数组降维:二维 $dp[i][j] \to$ 一维 $dp[j]$,省一维空间。
完全背包(每件无限取)¶
$$dp[j] = \max(dp[j],\ dp[j - w_i] + v_i), \quad j \text{ 从小到大遍历}$$
区别只有遍历方向——面试必问:01 逆序防重复,完全正序允许重复。
416 分割等和子集(01 背包变形)¶
能分成两个和相等的子集 $\iff$ 存在子集和为 $sum/2$($sum$ 必须为偶数):
$$dp[j] = dp[j] \lor dp[j - nums[i]]$$
518 零钱兑换 II(完全背包求方案数)¶
$$dp[j] = dp[j] + dp[j - coin] \quad (\text{先遍历硬币,防顺序不同的重复})$$
✍️ §3.1 手算 01 背包:C=5 装下 (w,v)=(2,3),(3,4),(4,5),最优是 7¶
$dp[i][c]=\max(dp[i-1][c],\ dp[i-1][c-w_i]+v_i)$——3 件物品、容量 5 手算填表,看懂"取或不取"。
设定:容量 $C=5$,物品:1 号 $(w_1=2,v_1=3)$、2 号 $(w_2=3,v_2=4)$、3 号 $(w_3=4,v_3=5)$。
第 1 步:只考虑物品 1($i=1$)
容量 $0,1$ 装不下→0;$c\ge2$ 全能装→3:$dp[1]=[0,0,3,3,3,3]$
第 2 步:加物品 2($i=2$,$c=5$ 时"取":$dp[1][5-3]+4=3+4=7$)
$dp[2]=[0,0,3,4,4,7]$
第 3 步:加物品 3($i=3$,$c=5$ 时"取" $dp[2][5-4]+5=0+5=5<7$ 不取)
$dp[3]=[0,0,3,4,5,7]\Rightarrow$ 最优值 $=7$(选物品 1+2,价值 $3+4=7$)
| c | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 物品1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 物品2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 物品3 | 0 | 0 | 3 | 4 | 5 | 7 |
手算收获:
- 转移就一句"取或不取":$c\ge w_i$ 才考虑取,取则腾出 $c-w_i$ 容量看 $i-1$ 行的最优——逆序滚动(本 notebook §3.1 白板演算)防同物品复用
- $dp[i][c]$ 只依赖上一行:内存可从 $O(nC)$ 压到 $O(C)$,这就是"滚动数组"
- 本例"不取"获胜(7 > 5):贪心按价值密度($3/2=1.5,4/3=1.33,5/4=1.25$)会选物品 1+3 = 8?不对,$w_1+w_3=6>C$ 装不下,贪心只能选 1+2=7——恰好同优,但这是巧合——01 背包必须 DP、贪心可能错(面试高频论证)
- 复杂度 $O(nC)$:$n$ 小 $C$ 大时是伪多项式,怀疑这条线就对了
下面 numpy 复算。
# ---- §3.1 验证:numpy 复算 01 背包填表 ----
import numpy as np
C, n = 5, 3
w, v = [2, 3, 4], [3, 4, 5]
dp = np.zeros((n + 1, C + 1), dtype=int)
for i in range(1, n + 1):
for c in range(C + 1):
dp[i][c] = dp[i - 1][c]
if c >= w[i - 1]:
dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1])
print(dp)
best = dp[n][C]
print(f'最优值 dp[3][5] = {best}')
assert best == 7
assert dp[1][2] == 3 and dp[2][5] == 7 and dp[3][4] == 5
print('\n✓ 与手算一致')
# ===== 01 背包 / 416 分割等和子集 / 518 零钱兑换 II =====
# 【题目目标】① 01 背包模板:每件物品最多取一次,求容量 W 下的最大价值;
# ② 416:能否把数组分成两个和相等的子集(01 背包判定);
# ③ 518:完全背包求凑成 amount 的组合方案数(顺序不同的算同一种)
# 【算法思路】滚动数组 dp[j]:容量为 j 时的最优值。01 背包内层容量 j 必须
# 逆序遍历——保证 dp[j-w] 读到的是上一轮(未取当前物品)的旧值,
# 防止同一物品被重复取;416 是 01 背包布尔版(target=sum/2);
# 518 是完全背包:内层正序允许硬币多次使用,且先遍历硬币再遍历金额
# (组合数语义,防 (1,2) 与 (2,1) 重复)
# 【变量含义】weights/values:物品重量与价值;W:背包容量;dp[j]:容量 j 的
# 最大价值 / 是否可凑出 / 方案数;total/target:总和与一半;
# x:当前元素;c:当前硬币面额
# 【循环不变量】01 背包每轮内层逆序,dp[j-w] 始终是上一轮的旧值 → 每件物品
# 至多被选一次
# 【递归终止】无递归;递推边界:价值/方案版 dp[0]=0,判定版 dp[0]=True
# 【关键边界】416:总和为奇数直接返回 False;518:dp[0]=1(不选任何硬币是一种
# 方案);内层循环下界为 w(或 c)避免负下标
# 【复杂度】01 背包/416:O(n·W)/O(n·target);518:O(|coins|·amount);
# 空间分别为 O(W)/O(target)/O(amount)
# 01 背包模板:每件物品最多取一次,容量 j 必须逆序遍历防止重复取
def knapsack_01(weights, values, W):
# 标准 01 背包模板:返回最大价值
dp = [0] * (W + 1) # dp[j]:容量为 j 时的最大价值
for w, v in zip(weights, values): # 遍历每件物品(重量 w、价值 v)
for j in range(W, w - 1, -1): # 逆序:防止同一物品重复取
dp[j] = max(dp[j], dp[j - w] + v) # 不装或装下当前物品,取更大价值
return dp[W] # 容量 W 下的最大价值即答案
# 416. 分割等和子集:能否分成两个和相等的子集,等价于能否凑出总和的一半
# 本质是 01 背包的判定问题:dp[j] 表示能否凑出子集和 j
def can_partition(nums):
total = sum(nums) # 数组元素的总和
if total % 2: # 总和为奇数时无法平分
return False # 尝试完仍失败,返回 False
target = total // 2 # 要凑出的目标子集和
dp = [False] * (target + 1) # dp[j]:能否凑出子集和 j
dp[0] = True # 和为 0 一定能凑出(一个都不选)
for x in nums: # 遍历每个元素
for j in range(target, x - 1, -1): # 逆序遍历容量:01 背包,每个数只用一次
dp[j] = dp[j] or dp[j - x] # 不选 x 或选 x,只要一条路可行即可
return dp[target] # 能否凑出总和的一半
# 518. 零钱兑换 II:完全背包求方案数,必须先遍历硬币再遍历金额(防顺序不同的重复)
def change(amount, coins):
# 完全背包:组合数(先硬币后金额)
dp = [0] * (amount + 1) # dp[j]:凑成金额 j 的方案数
dp[0] = 1 # 金额 0 只有一种方案:一个硬币都不选
for c in coins: # 遍历每种硬币
for j in range(c, amount + 1): # 正序:允许重复使用
dp[j] += dp[j - c] # 累加使用当前硬币的方案数
return dp[amount] # 凑成总金额的方案数
print('01背包(最大价值):', knapsack_01([1, 3, 4], [15, 20, 30], 4)) # 期望 35(1+3)
print('can_partition([1,5,11,5]) =', can_partition([1, 5, 11, 5])) # 期望 True
print('can_partition([1,2,5]) =', can_partition([1, 2, 5])) # 期望 False
print('change(5,[1,2,5]) =', change(5, [1, 2, 5])) # 期望 4
print('change(3,[2]) =', change(3, [2])) # 期望 0
01背包(最大价值): 35 can_partition([1,5,11,5]) = True can_partition([1,2,5]) = False change(5,[1,2,5]) = 4 change(3,[2]) = 0
§3.1 01 背包滚动数组:为什么容量必须逆序(白板演算)¶
具体例子:weights=[1,3,4], values=[15,20,30], 容量 W=4,期望最优 = 35(取物品 1 + 3:15+20)。
二维写法 dp[i][j](i 件物品、容量 j):
| i\j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1(w1,v1) | 0 | 15 | 15 | 15 | 15 |
| 2(w3,v3) | 0 | 15 | 15 | 20 | 35 |
| 3(w4,v4) | 0 | 15 | 15 | 20 | 35 |
一维滚动 dp[j]:第 i 行只依赖第 i-1 行旧值,所以原地更新时必须保证读到的还是旧值。
为什么逆序:内层 for j in range(W, w-1, -1),dp[j] = max(dp[j], dp[j-w]+v)。逆序时 dp[j-w] 是本轮尚未更新的旧值(第 i-1 行的结果);若正序,dp[j-w] 可能已被本行新值覆盖 → 同一件物品被取多次(退化成分数/完全背包)。
正序(错误): j=1 更新 dp[1]=15 → j=2 读 dp[1]=15(已被污染)→ dp[2]=30 ✗ 物品取了两次
逆序(正确): j=4 读 dp[3](旧值 0)→ ... → j=2 读 dp[1](本轮还没碰,旧值 0)→ dp[2]=15 ✓
💡 一句话记忆:逆序 = 保证每个容量只被"上一轮的结果"更新一次 → 每件物品最多取一次。
§4 最长类:LIS / LCS / 最长回文子串¶
300 最长递增子序列(LIS)¶
$$dp[i] = 1 + \max_{j < i,\ nums[j] < nums[i]} dp[j] \quad \Rightarrow \quad O(n^2)$$
贪心 + 二分优化 $O(n \log n)$:维护 tails[k] = 长度为 $k+1$ 的递增子序列的最小结尾;bisect_left 定位替换点——只更新最小结尾,不丢失更小值。
1143 最长公共子序列(LCS)¶
$$dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & a_i = b_j \\ \max(dp[i-1][j],\ dp[i][j-1]) & a_i \ne b_j \end{cases}$$
5 最长回文子串(区间 DP / 中心扩展)¶
区间 DP 判回文:
$$dp[i][j] = (s_i = s_j) \land dp[i+1][j-1]$$
复杂度:$O(n^2)$(中心扩展 $O(n^2)$ 但常数小,常被面试要求)
# ===== 最长类:LIS 300(贪心+二分)/ LCS 1143 / 最长回文子串 5 =====
# 【题目目标】① 300 最长递增子序列长度(O(n log n) 贪心二分版);② 1143 两个
# 字符串的最长公共子序列长度;③ 5 最长回文子串(区间 DP 判回文)
# 【算法思路】LIS:tails[k] 存「长度为 k+1 的递增子序列的最小结尾值」,tail 严格
# 递增,对每个 x 用 bisect_left 找第一个 ≥ x 的位置替换/追加;
# LCS:dp[i][j] 字符相等取左上角 +1,不等取上方/左方较大值;
# 回文子串:dp[i][j] 表示 s[i..j] 是否回文,两端相等且内部回文即真,
# 按区间长度 L 从小到大填表(区间 DP 关键遍历顺序)
# 【变量含义】tails:各长度下的最小结尾值;x:当前元素;i:二分定位/区间起点;
# a/b:两个字符串;dp 表;L:区间长度;j:右端点;start/max_len:
# 最长回文子串的起点与长度
# 【循环不变量】LIS 的 tails 严格递增(反证:若 tail[i]>=tail[j](i<j),长序列去尾
# 得更优短序列矛盾)→ 二分替换不丢最优解;LCS 每格只依赖上/左/左上
# 【递归终止】无递归;回文串初始化 dp[i][i]=True(单字符),n<2 直接返回 s
# 【关键边界】LIS 空数组 len=0;LCS 多一行一列哨兵、下标减一取字符;回文长度
# L=2 时需特判(dp[i+1][j-1] 区间为空);枚举 i 从 0 到 n-L
# 【复杂度】LIS O(n log n);LCS O(mn);回文 O(n²);空间 O(n)/O(mn)/O(n²)
# 引入 bisect_left,用于 LIS 的 O(n log n) 贪心 + 二分优化
from bisect import bisect_left
# 300. 最长递增子序列:贪心 + 二分,tails 维护各长度下的最小结尾值
def length_of_lis(nums):
tails = [] # tails[k]:长度为 k+1 的递增子序列的最小结尾值
for x in nums: # 遍历每个元素
i = bisect_left(tails, x) # 第一个 >= x 的位置
if i == len(tails):
tails.append(x)
else:
tails[i] = x # 更新最小结尾
return len(tails) # tails 的长度就是 LIS 的长度
# 1143. 最长公共子序列:字符相等时取左上角 +1,不等时取上方/左方的较大值
def longest_common_subsequence(a, b):
m, n = len(a), len(b) # 两个字符串的长度
dp = [[0] * (n + 1) for _ in range(m + 1)] # 二维 DP 表,多一行一列作哨兵
for i in range(1, m + 1): # 外层遍历第一个串(跳过哨兵行)
for j in range(1, n + 1): # 内层遍历第二个串(跳过哨兵列)
if a[i - 1] == b[j - 1]: # 当前两个字符相等
dp[i][j] = dp[i - 1][j - 1] + 1 # 左上角 + 1:公共子序列长度加一
else: # 当前字符不等
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 取上方或左方的较大值
return dp[m][n] # 右下角即最终答案
# 5. 最长回文子串:区间 DP 判回文,按区间长度从小到大填表
def longest_palindrome(s):
n = len(s) # 字符串长度
if n < 2: # 长度小于 2:整个串本身就是回文
return s # 直接返回原串
start, max_len = 0, 1 # 记录最长回文子串的起点与长度
dp = [[False] * n for _ in range(n)] # dp[i][j]:s[i..j] 是否为回文
for i in range(n): # 处理长度为 1 的区间
dp[i][i] = True # 单字符区间一定是回文,对角线置 True
# 按长度从小到大填表(区间 DP 遍历顺序)
for L in range(2, n + 1): # 按区间长度从小到大递推(区间 DP 关键顺序)
for i in range(n - L + 1): # 枚举区间起点
j = i + L - 1 # 区间右端点
if s[i] == s[j] and (L == 2 or dp[i + 1][j - 1]): # 两端相等且内部也是回文(长度 2 特判)
dp[i][j] = True # 标记该区间为回文
if L > max_len: # 找到更长的回文
start, max_len = i, L # 更新起点与最大长度
return s[start:start + max_len] # 截取最长回文子串返回
print('LIS([10,9,2,5,3,7,101,18]) =', length_of_lis([10, 9, 2, 5, 3, 7, 101, 18])) # 4
print('LIS([0,1,0,3,2,3]) =', length_of_lis([0, 1, 0, 3, 2, 3])) # 4
print('LCS(abcde,ace) =', longest_common_subsequence('abcde', 'ace')) # 3
print('LCS(abc,def) =', longest_common_subsequence('abc', 'def')) # 0
print('longest_palindrome(babad) =', longest_palindrome('babad')) # bab/aba
print('longest_palindrome(cbbd) =', longest_palindrome('cbbd')) # bb
LIS([10,9,2,5,3,7,101,18]) = 4 LIS([0,1,0,3,2,3]) = 4 LCS(abcde,ace) = 3 LCS(abc,def) = 0 longest_palindrome(babad) = bab longest_palindrome(cbbd) = bb
§4.1 为什么 LIS 的 O(n log n)(tails 二分)正确(证明)¶
定义:tails[k] = 长度为 k+1 的递增子序列的最小结尾值。
性质 1(单调递增):tails 严格递增。反证:若 tails[i] >= tails[j] (i<j),则长度为 j 的子序列的结尾 ≥ 长度为 i 的结尾,但长度为 j 的子序列去掉末尾就是一个长度为 i 的更优候选,矛盾。
性质 2(二分替换不丢最优解):对每个新数 x,找 pos = bisect_left(tails, x)(第一个 ≥ x 的位置)并替换。替换后:
- 以
tails[pos] = x结尾的长度 pos+1 子序列仍合法(前 pos 个元素都 < x,因为 tails 严格递增); tails[pos]变小只会让后续数更容易接上 → 不劣化任何已有分组。
结论:遍历一遍,每次 O(log n) 替换,总复杂度 O(n log n);最终答案 = len(tails)。
§5 编辑距离(LeetCode 72,必背推导)¶
题目:把 $A$ 变成 $B$ 的最少操作数(插入/删除/替换)。
状态:$dp[i][j]$ = $A$ 前 $i$ 个字符 → $B$ 前 $j$ 个字符的最小编辑距离。
转移方程(三种操作对应三项):
$$dp[i][j] = \begin{cases} dp[i-1][j-1] & a_i = b_j \\ 1 + \min\big(\underbrace{dp[i-1][j]}_{\text{删除} a_i},\ \underbrace{dp[i][j-1]}_{\text{插入} b_j},\ \underbrace{dp[i-1][j-1]}_{\text{替换}}\big) & a_i \ne b_j \end{cases}$$
初始化:$dp[i][0] = i$(全删),$dp[0][j] = j$(全插)。
复杂度:$O(mn)$ 时间,$O(mn)$ 空间(可滚动到 $O(m)$)。
§5.1 编辑距离 horse → ros 填表演算(白板标准演示)¶
dp[i][j] = word1[:i] → word2[:j] 最少操作数;dp[0][j]=j(插入 j 次)、dp[i][0]=i(删除 i 次)。
| dp | '' | r | o | s |
|---|---|---|---|---|
| '' | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
递推来源(取三方向最小值 + 替换代价):
$$dp[i][j] = \min\big(dp[i-1][j]+1 \ (删),\ dp[i][j-1]+1 \ (插),\ dp[i-1][j-1]+\mathbb{1}[word1_i \neq word2_j] \ (替/留)\big)$$
逐格来源示例:dp[2][2]("ho"→"ro")= min(dp[1][2]+1=3, dp[2][1]+1=3, dp[1][1]+0=1) = 1(o 与 o 相等保留)。答案 dp[5][3]=3(horse→ros 需 3 次:h→r、删 e、删 s 或等价操作)。
💡 填表顺序:行从左到右、列从上到下即可——因为每个格子只依赖上/左/左上,已在前面算好。
# ============== 编辑距离 72(必背填表推导) ==============
# 【题目目标】把 word1 变成 word2 所需的最少操作数(仅允许插入/删除/替换)
# 【算法思路】dp[i][j] = word1 前 i 个字符 → word2 前 j 个字符的最少操作数;
# 字符相等时直接继承左上角(该位无需操作);不等时取「删除 word1[i]」
# (dp[i-1][j])、「插入 word2[j]」(dp[i][j-1])、「替换」(dp[i-1][j-1])
# 三者最小值 + 1
# 【变量含义】m/n:两个字符串长度;dp:二维 DP 表(多一行一列作哨兵);
# i/j:word1/word2 的处理长度
# 【循环不变量】按行主序填表:每格只依赖上方、左方、左上,均已先算好
# 【递归终止】无递归;初始化 dp[i][0]=i(全部删除)、dp[0][j]=j(全部插入)
# 【关键边界】空串一侧:全删/全插;两个字符的索引要减一
# (word1[i-1] 是第 i 个字符);单字符相等时操作数为 0
# 【复杂度】时间 O(m·n);空间 O(m·n)(可滚动优化到 O(m))
# 72. 编辑距离:dp[i][j] 表示 word1 前 i 个字符变成 word2 前 j 个字符的最少操作数
def min_distance(word1, word2):
m, n = len(word1), len(word2) # 两个字符串的长度
dp = [[0] * (n + 1) for _ in range(m + 1)] # 二维 DP 表,多一行一列作哨兵
for i in range(m + 1):
dp[i][0] = i # 删除 i 次
for j in range(n + 1):
dp[0][j] = j # 插入 j 次
for i in range(1, m + 1): # 外层遍历第一个串(跳过哨兵行)
for j in range(1, n + 1): # 内层遍历第二个串(跳过哨兵列)
if word1[i - 1] == word2[j - 1]: # 当前字符相等:无需操作
dp[i][j] = dp[i - 1][j - 1] # 直接继承左上角(这个字符不用改)
else: # 当前字符不等
dp[i][j] = 1 + min(dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1]) # 替换
return dp[m][n] # 右下角即最终答案
print('horse->ros =', min_distance('horse', 'ros')) # 期望 3
print('intention->execution =', min_distance('intention', 'execution')) # 期望 5
print('空串->abc =', min_distance('', 'abc')) # 期望 3
print('a->a =', min_distance('a', 'a')) # 期望 0
horse->ros = 3 intention->execution = 5 空串->abc = 3 a->a = 0
§6 区间 DP:最长回文子序列(516)¶
状态:$dp[i][j]$ = 子串 $s[i..j]$ 的最长回文子序列长度。
转移(按区间长度从短到长):
$$dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & s_i = s_j \\ \max(dp[i+1][j],\ dp[i][j-1]) & s_i \ne s_j \end{cases}$$
遍历顺序:外层枚举区间长度、内层枚举起点——保证 dp[i+1][j-1] 已先被算到(这是区间 DP 与普通二维 DP 最大的区别)。
复杂度:$O(n^2)$ 时间、$O(n^2)$ 空间(可滚动 $O(n)$)。
💡 类似题:戳气球 312、合并石头的最低成本 1000——先想「最后一步合并/分割」确定区间转移。
# ============== 516 最长回文子序列(区间 DP) ==============
# 【题目目标】求字符串 s 的「最长回文子序列」长度(子序列不要求连续)
# 【算法思路】区间 DP:dp[i][j] = s[i..j] 的最长回文子序列长度;两端字符相等时
# 取内部区间结果 +2;不等时取去掉左端或右端的较大值;按区间长度 L
# 从小到大填表,保证 dp[i+1][j-1](更小区间)先被算好
# 【变量含义】n:字符串长度;dp 表;L:区间长度;i:区间起点;j:区间右端点
# 【循环不变量】外层按区间长度递增、内层按起点递增(区间 DP 与普通二维 DP 的
# 最大区别——保证短区间先于长区间计算)
# 【递归终止】无递归;初始化单字符区间 dp[i][i]=1;空串特判直接返回 0
# (避免访问 dp[0][-1] 越界)
# 【关键边界】空串输入返回 0;L 从 2 起、i 从 0 到 n-L;两端相等才 +2
# 【复杂度】时间 O(n²);空间 O(n²)(可滚动到 O(n))
# 516. 最长回文子序列:区间 DP,按区间长度从小到大递推
def longest_palindrome_subseq(s):
if not s: # 空串直接返回 0(避免 dp[0][-1] 越界)
return 0 # 返回 0
n = len(s) # 字符串长度
dp = [[0] * n for _ in range(n)]
for i in range(n): # 处理长度为 1 的区间
dp[i][i] = 1
for L in range(2, n + 1): # 区间长度
for i in range(0, n - L + 1): # 起点
j = i + L - 1 # 区间右端点
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2 # 两端相等:内部最长回文长度 + 2
else: # 当前字符不等
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) # 两端不等:取去掉左端或右端的较大值
return dp[0][n - 1]
print('bbbab =', longest_palindrome_subseq('bbbab')) # 期望 4(bbbb)
print('cbbd =', longest_palindrome_subseq('cbbd')) # 期望 2(bb)
print('a =', longest_palindrome_subseq('a')) # 期望 1
print('空 =', longest_palindrome_subseq('')) # 期望 0
bbbab = 4 cbbd = 2 a = 1 空 = 0
§7 股票系列(状态机套路,一类题全通)¶
通用状态机:每天两种状态——持有(hold)或空仓(empty):
- $hold[i]$:第 $i$ 天结束后持有股票的最大利润
- $empty[i]$:第 $i$ 天结束后空仓的最大利润
$$hold[i] = \max(hold[i-1],\ empty[i-1] - prices[i]) \quad (\text{买入})$$
$$empty[i] = \max(empty[i-1],\ hold[i-1] + prices[i]) \quad (\text{卖出})$$
各题目差异:
| 题 | 限制 | 改动 |
|---|---|---|
| 121 | 一次 | 记录一次到手利润 |
| 122 | 无限次 | 上述两式(可当日先卖后买) |
| 309 | 含冷冻期 | 空仓状态拆成「今天卖出 / 冷冻中」 |
| 714 | 含手续费 | 卖出时减去 $fee$ |
| 123/188 | 至多 k 次 | 状态加维度 $[k]$(第几次交易) |
# ===== 股票状态机:122 无限次 / 714 手续费 / 188 至多 k 次 =====
# 【题目目标】用「状态机」统一求解股票系列:122 无限次交易、714 加手续费、
# 188 至多 k 次交易,返回最大利润
# 【算法思路】每天两个状态滚动更新:hold(持股)与 empty(空仓)。
# 122/714:new_hold=max(hold, empty-p)(继续持有或买入);
# new_empty=max(empty, hold+p-fee)(继续空仓或卖出扣手续费);
# 188:给状态加交易次数维度 hold[j]/sold[j] = 进行/完成第 j 次交易
# 【变量含义】prices:价格数组;fee:手续费;hold/empty:持股/空仓最大收益;
# hold[j]/sold[j]:第 j 次交易中的持仓/已完交易收益;k:交易次数上限
# 【循环不变量】每轮滚动后 hold/empty 均为「到当天为止」的最优值
# 【递归终止】无递归;初始化 hold=-inf(从未买入)、empty=0
# 【关键边界】188 中 k=0 或无价格数据直接返回 0;714 卖出时减去 fee;hold 初始
# 为 -inf 保证第一次买入必然执行 empty-p
# 【复杂度】122/714:O(n) 时间、O(1) 空间;188:O(n·k) 时间、O(k) 空间
# 122/714. 股票状态机:无限次交易 + 可选手续费,持股/空仓两状态滚动更新
def max_profit_any(prices, fee=0):
# 122/714:无限次交易,可选手续费
hold = float('-inf') # 持有股票
empty = 0 # 空仓
for p in prices: # 遍历每个交易日的价格
new_hold = max(hold, empty - p) # 今天持股:继续持有,或今天空仓买入
new_empty = max(empty, hold + p - fee) # 今天空仓:继续空仓,或今天卖出(扣手续费)
hold, empty = new_hold, new_empty # 滚动更新两个状态
return empty # 最终空仓(已清仓)的收益即最大利润
# 188. 至多 k 次交易:给状态加上交易次数维度,hold[j]/sold[j] 表示进行到第 j 次交易
def max_profit_k(prices, k):
# 188:至多 k 次交易(经典状态机三维可滚动)
if k == 0 or not prices: # 不能交易或没有价格数据
return 0 # 返回 0
# dp[j][0]=第j次交易后持仓, dp[j][1]=完成第j次交易
hold = [float('-inf')] * (k + 1) # hold[j]:进行到第 j 次交易时持仓的最大收益
sold = [0] * (k + 1) # sold[j]:完成第 j 次交易(空仓)的最大收益
for p in prices: # 遍历每个交易日的价格
for j in range(1, k + 1): # 对每一笔交易次数做状态转移
hold[j] = max(hold[j], sold[j - 1] - p) # 第 j 次买入:在之前空仓状态下花钱买入
sold[j] = max(sold[j], hold[j] + p) # 第 j 次卖出:在持仓状态下卖出获利
return sold[k] # 完成至多 k 次交易并最终空仓的最大收益
print('122 无限次 [7,1,5,3,6,4] =', max_profit_any([7, 1, 5, 3, 6, 4])) # 7
print('714 含手续费 [1,3,2,8,4,9], fee=2 =', max_profit_any([1, 3, 2, 8, 4, 9], 2)) # 8
print('188 至多2次 [3,3,5,0,0,3,1,4] =', max_profit_k([3, 3, 5, 0, 0, 3, 1, 4], 2)) # 6
print('188 至多2次 [1,2,3,4,5] =', max_profit_k([1, 2, 3, 4, 5], 2)) # 4
122 无限次 [7,1,5,3,6,4] = 7 714 含手续费 [1,3,2,8,4,9], fee=2 = 8 188 至多2次 [3,3,5,0,0,3,1,4] = 6 188 至多2次 [1,2,3,4,5] = 4
# ===== 路径类:62 不同路径 / 64 最小路径和 =====
# 【题目目标】① 62:网格 m×n 从左上到右下每次只能向下/向右,求不同路径数;
# ② 64:网格中带权值,求左上到右下经过格子和的最小路径和
# 【算法思路】62 组合数解法:总步数 m+n-2,选 m-1 步向下,答案 C(m+n-2, m-1);
# DP 滚动版:每格方案数 = 上方 + 左方,dp[j] 滚动一行;
# 64:原地更新,grid[i][j] += min(上方路径和, 左方路径和)
# 【变量含义】m/n:行数/列数;dp:滚动数组(第一行全 1);grid:权值网格;
# up/left:上方/左方格子的累计路径和(越界方向视为无穷大)
# 【循环不变量】滚动 dp[j] 更新完即第 i 行的值:dp[j] = 上一行同列 + 本行左列
# 【递归终止】无递归;62 边界:第一行与第一列方案数全为 1;64 起点格不更新
# 【关键边界】64 中第一行取不到上方、第一列取不到左方 → 用 float('inf') 表示;
# 单格输入 grid[[1]] 应返回 1
# 【复杂度】62 组合数 O(1) 时间/DP O(mn);64 O(mn) 时间、原地 O(1) 额外空间
# 引入 math,用于计算组合数
import math
# 62. 不同路径(组合数解法):总步数 m+n-2,选 m-1 步向下,C(m+n-2, m-1)
def unique_paths(m, n):
# 组合数解:C(m+n-2, m-1),空间 O(1)
return math.comb(m + n - 2, m - 1)
# 62. 不同路径(DP 滚动数组版):每格方案数 = 上方方案数 + 左方方案数
def unique_paths_dp(m, n):
dp = [1] * n # 滚动数组:第一行全 1
for _ in range(1, m): # 从第二行开始逐行更新
for j in range(1, n): # 除第一列外逐格更新
dp[j] += dp[j - 1] # dp[j] = 上一行同列 + 本行左列
return dp[n - 1] # 右下角的方案数
# 64. 最小路径和:原地更新,每格累加上方/左方路径和的较小值
def min_path_sum(grid):
m, n = len(grid), len(grid[0]) # 网格的行数与列数
for i in range(m): # 逐行处理
for j in range(n): # 逐列处理
if i == 0 and j == 0: # 起点格子不参与更新
continue # 起点直接跳过
up = grid[i - 1][j] if i > 0 else float('inf') # 上方格子的路径和(第一行视为无穷大)
left = grid[i][j - 1] if j > 0 else float('inf') # 左方格子的路径和(第一列视为无穷大)
grid[i][j] += min(up, left) # 原地更新
return grid[m - 1][n - 1] # 右下角累加完毕即为最小路径和
print('unique_paths(3,7) =', unique_paths(3, 7), '==', unique_paths_dp(3, 7)) # 28
print('unique_paths(3,2) =', unique_paths(3, 2)) # 3
print('min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) =',
min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # 期望 7
print('min_path_sum([[1]]) =', min_path_sum([[1]])) # 期望 1
unique_paths(3,7) = 28 == 28 unique_paths(3,2) = 3 min_path_sum([[1,3,1],[1,5,1],[4,2,1]]) = 7 min_path_sum([[1]]) = 1
§9 记忆化搜索示例(自顶向下)¶
以爬楼梯为例对比两种写法;记忆化 = 递归 + 缓存,不用想遍历顺序,适合区间 DP 等难推顺序的题:
from functools import lru_cache
@lru_cache(None)
def climb(n):
if n <= 2:
return n
return climb(n - 1) + climb(n - 2)
何时选记忆化:状态空间复杂、遍历顺序难确定(区间/树形 DP);何时选递推:需要空间优化(滚动数组)或面试官要求 $O(1)$ 空间。
# ===== 记忆化搜索(自顶向下):70 爬楼梯 / 139 单词拆分 =====
# 【题目目标】演示 DP 的另一种写法——记忆化搜索(递归 + 缓存):① 70 爬楼梯;
# ② 139 判断字符串 s 能否由词典中的单词完整拼接
# 【算法思路】记忆化 = 自顶向下 DP,不用考虑遍历顺序:① 爬楼梯直接用
# lru_cache(None) 缓存递归结果;② 139 用 dfs(i) 判断 s[i:] 能否拆完:
# 枚举切点 j,若前缀 s[i:j] 在词表且剩余部分 dfs(j) 可拆则成功
# 【变量含义】n:台阶数;s:输入串;word_dict/wd:词典(转 set 使查询 O(1));
# i:当前待拆的起点;j:本次切出的单词终点
# 【循环不变量】lru_cache 保证同一参数组合只计算一次(重叠子问题剪枝)
# 【递归终止】70:n<=2 时直接返回 n;139:i==len(s) 表示拆到末尾,返回 True
# 【关键边界】139 枚举 j 从 i+1 到 len(s)(含终点),必须前缀在词表才继续递归;
# 词表需转集合 O(1) 查询;递归深度受字符串长度限制
# 【复杂度】70:O(n);139:状态 O(n) × 每状态枚举切点 O(n) → O(n²)
# 记忆化搜索(自顶向下)示例:lru_cache 缓存爬楼梯递归结果;单词拆分 139 用 dfs(i) 判断 s[i:] 能否拆完
from functools import lru_cache
@lru_cache(None)
# 70. 爬楼梯(记忆化版本):lru_cache(None) 自动缓存递归结果,自顶向下写法
def climb_memo(n):
if n <= 2:
return n
return climb_memo(n - 1) + climb_memo(n - 2) # 第 n 阶 = 第 n-1 阶 + 第 n-2 阶
print('记忆化 climb(10) =', climb_memo(10), '(递推版 =', climb_stairs(10), ')') # 89
# 记忆化的经典场景:单词拆分 139
# 139. 单词拆分:前缀匹配 + 记忆化搜索,能把 s 拆到末尾即成功
def word_break(s, word_dict):
wd = set(word_dict) # 单词表转成集合,O(1) 查询
@lru_cache(None)
def dfs(i): # dfs(i):判断 s[i:] 能否被完整拆分
if i == len(s): # 已处理到末尾:拆分成功
return True # 返回成功
for j in range(i + 1, len(s) + 1): # 枚举本次要切出的单词终点
if s[i:j] in wd and dfs(j): # 前缀在词表且剩余部分也能拆
return True # 找到一种可行拆分
return False # 尝试完仍失败,返回 False
return dfs(0) # 从字符串开头开始判断
print('word_break(leetcode, [leet, code]) =', word_break('leetcode', ['leet', 'code'])) # True
print('word_break(applespenapple, [apple, pen]) =', word_break('applepenapple', ['apple', 'pen'])) # True
print('word_break(catsandog, [cats, dog, sand, and, cat]) =',
word_break('catsandog', ['cats', 'dog', 'sand', 'and', 'cat'])) # False
记忆化 climb(10) = 89 (递推版 = 89 ) word_break(leetcode, [leet, code]) = True word_break(applespenapple, [apple, pen]) = True word_break(catsandog, [cats, dog, sand, and, cat]) = False
§10 常见 bug 与边界(面试踩坑区)¶
- 状态定义含糊:
dp[i]是「前 i 个」还是「第 i 个」,差一个下标错一片 - 初始化遗漏:编辑距离的第 0 行/第 0 列、背包的
dp[0]、LCS 的哨兵行 - 01 背包忘了逆序:正序 = 完全背包,答案直接错(面试高频抓错点)
- 区间 DP 遍历顺序错:外层必须是区间长度,否则
dp[i+1][j-1]还没算 - 越界:
dp[i-2]、dp[j-w]要判断下标;爬楼梯n=0/1特判 - max 初始化:路径和类初始
-inf而不是 0(可能有负数);最长类别忘记单元素情况 - 贪心误判 DP:
[1,2,3]类递增题贪心也能过,面试别急着写贪心,先说「有重叠子问题,用 DP」 - 空间复杂度:能滚动就滚动(一维化),面试官爱问「还能优化空间吗」
§11 面试追问与扩展(加分项)¶
11.1 为什么 01 背包要逆序遍历(推导)¶
一维滚动时 dp[j-w] 若已在本轮更新过,说明该物品已被取了一次 → 等价无限次。逆序保证 dp[j-w] 还是上一轮(未取该物品)的值。
11.2 复杂度回答模板¶
「状态数 × 转移成本:状态 $O(n^2)$、每状态转移 $O(1)$ → 总 $O(n^2)$,滚动数组可优化空间到 $O(n)$。」
11.3 DP 与贪心的边界¶
贪心 = 每一步局部最优即全局最优(区间调度、跳跃游戏);DP = 需要比较多个子方案。经典辩题:硬币找零(面额 [1,3,4] 贪心在 amount=6 会错:贪心 4+1+1=3 枚,最优 3+3=2 枚)。
11.4 进阶方向¶
- 数位 DP(面试少见)、状压 DP(TSP 类,
dp[mask]) - 树形 DP(打家劫舍 III)
- DP 优化:斜率优化 / 四边形不等式(多为竞赛,秋招面试基本到「滚动数组」为止)
§12 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 爬楼梯(LeetCode 70)
- 2. 打家劫舍(198)
- 3. 最大子数组和(53)
- 4. 买卖股票的最佳时机(121)
- 5. 不同路径(62)
- 6. 最小路径和(64)
- 7. 爬楼梯变体:使用最小花费爬楼梯(746)
- 8. 零钱兑换(322,完全背包最小值)
- 9. 最长递增子序列(300)
- 10. 最长公共子序列(1143)
L2 进阶(10 题)¶
- 11. 编辑距离(72)
- 12. 分割等和子集(416)
- 13. 零钱兑换 II(518)
- 14. 最长回文子串(5)
- 15. 最长回文子序列(516)
- 16. 单词拆分(139)
- 17. 乘积最大子数组(152)
- 18. 完全平方数(279)
- 19. 买卖股票的最佳时机含冷冻期(309)
- 20. 不同的二叉搜索树(96,卡特兰)
L3 挑战(5 题)¶
- 21. 戳气球(312,区间 DP)
- 22. 买卖股票的最佳时机 IV(188,k 次状态机)
- 23. 最大矩形(85,直方图栈 + DP)
- 24. 俄罗斯套娃信封问题(354,LIS 升级)
- 25. 编辑距离变体:两个字符串的删除操作(583)
自测要点¶
- 5 分钟内盲写:70 + 198 + 53 + 121
- 能口述 01 背包逆序原因与完全背包正序原因
- 编辑距离转移方程在纸上推一遍(含三个操作的对应关系)
# ===== 高频补:322 零钱兑换 / 152 乘积 / 279 完全平方数 / 746 爬楼梯 =====
# 【题目目标】① 322:硬币面额数组 coins,凑成 amount 的最少硬币数(每枚可无限
# 用);② 152:乘积最大子数组;③ 279:用完全平方数(1,4,9,...)凑出
# n 的最少个数;④ 746:使用最小花费爬楼梯(可从 0/1 级起跳)
# 【算法思路】322 完全背包最小值:dp[j]=min(dp[j], dp[j-c]+1),内层正序允许
# 每枚硬币多次使用;152:同时维护当前最大/最小乘积(负负得正,负数
# 会翻转大小关系,故先交换 cur_max/cur_min);279:dp[i]=min(dp[i],
# dp[i-k*k]+1);746:dp[i]=min(dp[i-1],dp[i-2])+cost[i],滚动两变量
# 【变量含义】coins:硬币面额;amount:目标金额;dp[j]/dp[i]:DP 数组;x:当前
# 元素;cur_max/cur_min/best:当前最大/最小乘积与全局最优;k:平方数;
# a/b:爬楼梯滚动变量(前两级的最小花费)
# 【循环不变量】滚动变量始终保存至当前下标为止的最优子问题解
# 【递归终止】无递归;边界 dp[0]=0(凑 0 元 0 枚/0 个平方数)
# 【关键边界】322 凑不出返回 -1;152 负数先交换 max/min 再乘;279 只枚举 k*k<=i;
# 746 n=0/1 特判,最后可越过末级取 min(a,b)
# 【复杂度】322:O(|coins|·amount);152:O(n);279:O(n√n);746:O(n);
# 空间 O(amount)/O(1)/O(n)/O(1)
## §12.1 高频补:322 / 152 / 279 / 746
# 322. 零钱兑换:完全背包求最少硬币数,内层正序允许每枚硬币多次使用
def coin_change(coins, amount):
"""322 零钱兑换:完全背包最小值,内层正序(每枚可多次)。"""
dp = [float('inf')] * (amount + 1) # dp[j]:凑成金额 j 的最少硬币数,初始为无穷大
dp[0] = 0 # 凑 0 元需要 0 枚硬币
for c in coins: # 遍历每种硬币
for j in range(c, amount + 1): # 正序遍历金额:硬币可多次使用
dp[j] = min(dp[j], dp[j - c] + 1) # 不选或选当前硬币,取更少的枚数
return dp[amount] if dp[amount] != float('inf') else -1 # 凑不出时返回 -1
# 152. 乘积最大子数组:同时维护当前最大/最小乘积(负负得正,最小可能翻盘)
def max_product(nums):
"""152 乘积最大子数组:同时维护最大/最小(负负得正)。"""
cur_max = cur_min = best = nums[0] # 当前最大/最小乘积与全局最优,初始为第一个元素
for x in nums[1:]: # 从第二个元素开始遍历
if x < 0: # 负数会翻转乘积的大小关系
cur_max, cur_min = cur_min, cur_max # 乘负数后大小互换
cur_max = max(x, cur_max * x) # 要么新开一段,要么续乘,取较大
cur_min = min(x, cur_min * x) # 同时维护最小乘积,供负负得正时翻盘
best = max(best, cur_max)
return best # 返回最优答案
# 279. 完全平方数:dp[j] = min(dp[j], dp[j - k*k] + 1),完全背包求最少个数
def num_squares(n):
"""279 完全平方数:dp[j] = min(dp[j], dp[j-k*k]+1)。"""
dp = [0] + [float('inf')] * n # dp[i]:凑出 i 需要的最少完全平方数
for i in range(1, n + 1): # 从 1 到 n 逐个计算
k = 1 # 从 1 开始尝试平方数
while k * k <= i: # 平方数不超过 i 时继续
dp[i] = min(dp[i], dp[i - k * k] + 1) # 用 k*k 补齐,取最少个数
k += 1 # 尝试更大的平方数
return dp[n] # dp[n] 即最少个数
# 746. 使用最小花费爬楼梯:dp[i] = min(dp[i-1], dp[i-2]) + cost[i],滚动变量 O(1) 空间
def min_cost_climbing(cost):
"""746 使用最小花费爬楼梯:dp[i] = min(dp[i-1], dp[i-2]) + cost[i]。"""
n = len(cost) # 台阶个数
if n == 0: return 0 # 没有台阶:花费 0
if n == 1: return cost[0] # 只有一级台阶:花费就是它本身
a, b = cost[0], cost[1] # 到前两级台阶的最小花费(滚动变量)
for i in range(2, n): # 从第 2 级开始递推
a, b = b, min(a, b) + cost[i] # 取前两级中较小者,加上本级花费
return min(a, b) # 可以越过最后一级,取前两级中较小者
print('coin_change([1,2,5], 11) =', coin_change([1, 2, 5], 11), '(期望 3)')
print('coin_change([2], 3) =', coin_change([2], 3), '(期望 -1)')
print('coin_change([1], 0) =', coin_change([1], 0), '(期望 0)')
print('max_product([2,3,-2,4]) =', max_product([2, 3, -2, 4]), '(期望 6)')
print('max_product([-2,0,-1]) =', max_product([-2, 0, -1]), '(期望 0)')
print('num_squares(12) =', num_squares(12), '(期望 3)')
print('num_squares(13) =', num_squares(13), '(期望 2)')
print('min_cost_climbing([10,15,20]) =', min_cost_climbing([10, 15, 20]), '(期望 15)')
coin_change([1,2,5], 11) = 3 (期望 3) coin_change([2], 3) = -1 (期望 -1) coin_change([1], 0) = 0 (期望 0) max_product([2,3,-2,4]) = 6 (期望 6) max_product([-2,0,-1]) = 0 (期望 0) num_squares(12) = 3 (期望 3) num_squares(13) = 2 (期望 2) min_cost_climbing([10,15,20]) = 15 (期望 15)