09_动态规划

经典题型

---

三、背包问题

背包问题是 DP 中最经典的模型之一，很多看似无关的题目都能转化为背包问题。

0-1 背包

问题描述：有 n 件物品和一个容量为 W 的背包。第 i 件物品重量 weight[i]，价值 value[i]。每件物品只能用一次，求能装入背包的最大价值。

1. 状态定义：dp[i][j] = 考虑前 i 件物品、背包容量为 j 时的最大价值
2. 转移方程：
   • 不选第 i 件：dp[i][j] = dp[i-1][j]
   • 选第 i 件（前提 j >= weight[i]）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]
   • 取两者最大值

二维代码：

def knapsack_01(weight: list[int], value: list[int], W: int) -> int:
    n = len(weight)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i - 1][j]  # 不选第 i 件
            if j >= weight[i - 1]:    # 能装下时，考虑选
                dp[i][j] = max(dp[i][j], dp[i - 1][j - weight[i - 1]] + value[i - 1])
    return dp[n][W]

空间优化（一维滚动数组）：

关键：内层循环从大到小遍历，确保每件物品只被选一次。

def knapsack_01_optimized(weight: list[int], value: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for i in range(len(weight)):
        # 必须倒序遍历，防止同一轮中物品被重复选取
        for j in range(W, weight[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[W]

分割等和子集（LC 416）

给定一个只包含正整数的非空数组 nums，判断是否可以将其分割成两个子集，使两个子集的元素和相等。

转化思路：总和为 S，问题等价于”能否从数组中选出若干个数，使其和恰好等于 S/2”。这就是一个容量为 S/2 的 0-1 背包问题。

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:  # 奇数不可能平分
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # 和为 0 总是可行的
    for num in nums:
        # 倒序遍历，0-1 背包的标准做法
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

---

四、字符串 DP

两个字符串之间的比较、匹配、变换，往往用二维 DP 解决。

最长公共子序列（LC 1143）

给定两个字符串 text1 和 text2，返回它们的最长公共子序列的长度。

1. 状态定义：dp[i][j] = text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度
2. 转移方程：
   • 如果 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
   • 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

用一个表格来理解（以 “ace” 和 “abcde” 为例）：

     ""  a  b  c  d  e
""    0  0  0  0  0  0
a     0  1  1  1  1  1
c     0  1  1  2  2  2
e     0  1  1  2  2  3

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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]

---

五、区间 DP 与树形 DP（进阶）

区间 DP

区间 DP 处理的是”在一个区间上做决策”的问题，状态一般定义为 dp[i][j] 表示区间 [i, j] 的最优解。

遍历顺序的关键：区间长度从小到大，先处理短区间，再处理长区间。

最长回文子序列（LC 516）

https://leetcode.cn/problems/longest-palindromic-subsequence/

给定一个字符串 s，找到其中最长的回文子序列的长度。子序列不要求连续。

五步法分析：

1. 状态定义：dp[i][j] = s[i..j] 中最长回文子序列的长度
2. 转移方程：
   • 如果 s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2（首尾配对，中间取最优）
   • 否则：dp[i][j] = max(dp[i+1][j], dp[i][j-1])（丢弃左端或右端）
3. 初始化：dp[i][i] = 1（单个字符本身就是回文，长度为 1）
4. 遍历顺序：区间长度从 2 到 n，左端点 i 从 n-2 到 0
5. 返回值：dp[0][n-1]

def longestPalindromeSubseq(self, s: str) -> int:
	n = len(s)
	dp = [[0] * n for _ in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i][i] = 1
		for j in range(i + 1, n):
			if s[i] == s[j]:
				dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	return dp[0][n - 1]

戳气球（LC 312）

https://leetcode.cn/problems/burst-balloons/

有 n 个气球，编号 0 到 n-1，每个气球上标有一个数字。戳破气球 i 可以获得 nums[left] * nums[i] * nums[right] 个硬币。求能获得的最大硬币数。

关键技巧：在数组两端各添加一个值为 1 的虚拟气球，然后思考”哪个气球最后被戳破”（而不是先戳哪个），这样戳破第 k 个气球时，左右两侧已经是独立的子问题了。

五步法分析：

1. 状态定义：dp[i][j] = 戳破开区间 (i, j) 内所有气球能获得的最大硬币数
2. 转移方程：枚举区间内最后戳破的气球 k
   dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])，其中 i < k < j
3. 初始化：dp[i][j] = 0（区间内没有气球时，硬币数为 0）
4. 遍历顺序：区间长度从 2 到 n+1（因为两端有虚拟气球）
5. 返回值：dp[0][n+1]（0 和 n+1 是虚拟气球）

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        # 两端添加虚拟气球
        nums = [1] + nums + [1]
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        
        for i in range(n - 1, -1, -1):          # 区间左端点，从下往上
            for j in range(i + 2, n + 2):       # 区间右端点，从左往右
                for k in range(i + 1, j):       # 枚举最后戳破的气球 k
                    dp[i][j] = max(dp[i][j],
                                   dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])
        return dp[0][n + 1]

树形 DP

在树结构上做 DP，通常用 DFS 后序遍历，先递归处理子节点，再把子节点的结果汇总到父节点。

打家劫舍 III（LC 337）

在二叉树上偷东西，如果两个直接相连的房子在同一天晚上被打劫，房屋将报警。求能偷到的最高金额。

思路：每个节点需要返回两个状态——选/不选当前节点时的最大金额。用元组 (不选, 选) 表示。

1. 不选当前节点：左右子节点可以自由选择，取各自的最大值相加
2. 选当前节点：左右子节点都不能选，只能取”不选”的值再加上当前节点的值

def rob(root: TreeNode | None) -> int:
    def dfs(node):
        if not node:
            return (0, 0)  # (不选, 选)
        left = dfs(node.left)
        right = dfs(node.right)
        # 不选当前节点：左右子树各自取最大值
        not_rob = max(left) + max(right)
        # 选当前节点：左右子树只能取"不选"
        do_rob = left[0] + right[0] + node.val
        return (not_rob, do_rob)
    return max(dfs(root))

二叉树的直径（LC 543）

给定一棵二叉树，计算它的直径长度（任意两个节点间路径长度的最大值）。

思路：直径一定经过某个节点，此时直径 = 该节点左子树深度 + 右子树深度。用 DFS 求每个节点的深度时，顺便更新全局最大直径。

def diameterOfBinaryTree(root: TreeNode | None) -> int:
    diameter = 0

    def depth(node):
        nonlocal diameter
        if not node:
            return 0
        left_depth = depth(node.left)
        right_depth = depth(node.right)
        # 更新直径：经过当前节点的最长路径
        diameter = max(diameter, left_depth + right_depth)
        return max(left_depth, right_depth) + 1

    depth(root)
    return diameter

---

经典题目清单

入门级

题号	题目	核心思路
LC 70	爬楼梯	斐波那契递推
LC 509	斐波那契数	最基础的 DP
LC 746	使用最小花费爬楼梯	爬楼梯变体

基础级

题号	题目	核心思路
LC 53	最大子数组和	线性 DP
LC 198	打家劫舍	选或不选
LC 62	不同路径	网格 DP
LC 64	最小路径和	网格 DP
LC 322	零钱兑换	完全背包

进阶级

题号	题目	核心思路
LC 416	分割等和子集	0-1 背包
LC 1143	最长公共子序列	字符串 DP
LC 72	编辑距离	字符串 DP
LC 300	最长递增子序列	线性 DP + 二分优化
LC 516	最长回文子序列	区间 DP
LC 312	戳气球	区间 DP
LC 337	打家劫舍 III	树形 DP
LC 543	二叉树的直径	树形 DP

---

小结

动态规划的核心就是两件事：状态定义和状态转移方程。

推荐的学习路径：

1. 先写暴力递归：不考虑效率，用递归把问题解出来
2. 加记忆化：在递归基础上加一个缓存（字典或数组），消除重复计算
3. 改写为 DP 表：把自顶向下的递归改成自底向上的循环
4. 空间优化：如果 dp[i] 只依赖 dp[i-1]，就可以用滚动变量代替整个数组

暴力递归 → 记忆化搜索 → DP 表 → 空间优化

记住：DP 题目做多了自然就有感觉了。每道题都用五步法分析，刻意练习，很快就能在面试中游刃有余。

---

模板速查

以下为常用 DP 模板的浓缩版（背包 / 计数 / LIS / LCS / 编辑距离 / 区间 DP），复习时快速过一遍：

动态规划

# ===== 1. 背包问题 =====
# 01 背包（每个物品选0或1次）
def knapsack_01(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(W, weights[i] - 1, -1):  # 倒序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 完全背包（每个物品可选无限次）
def knapsack_complete(n, W, weights, values):
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # 正序遍历
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

# 多重背包（每个物品可选有限次）- 二进制优化
def knapsack_multi(n, W, weights, values, counts):
    items = []  # 转化为01背包
    for i in range(n):
        k = 1
        c = counts[i]
        while c > 0:
            take = min(k, c)
            items.append((weights[i] * take, values[i] * take))
            c -= take
            k *= 2
    dp = [0] * (W + 1)
    for w, v in items:
        for j in range(W, w - 1, -1):
            dp[j] = max(dp[j], dp[j - w] + v)
    return dp[W]

# ===== 计数DP（爬楼梯/骰子问题）=====
# 每次可以走1~k步，求到达n级台阶的走法数
def count_ways(n, k):
    dp = [0] * (n + 1)
    dp[0] = 1  # 基础情况：到达0级只有1种方式（不走）
    for i in range(1, n + 1):
        dp[i] = sum(dp[max(0, i-k):i]) % MOD
    return dp[n]

# 简化为：每次走1~6步（骰子问题）
dp = [1]
for i in range(int(input())):
    dp.append(sum(dp[-6:]) % MOD)
print(dp[-1])

# ===== 2. 最长上升子序列 (LIS) =====
def lis(arr):
    import bisect
    dp = []
    for x in arr:
        pos = bisect.bisect_left(dp, x)
        if pos == len(dp):
            dp.append(x)
        else:
            dp[pos] = x
    return len(dp)

# ===== 3. 最长公共子序列 (LCS) =====
def lcs(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

# ===== 4. 编辑距离 =====
def edit_distance(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][0] = i
    for j in range(m+1):
        dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[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[n][m]

# ===== 5. 区间 DP =====
def interval_dp(n, cost):
    # dp[i][j] = 合并 i~j 的最小代价
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            dp[i][j] = min(dp[i][k] + dp[k+1][j] for k in range(i, j))
    return dp[0][n-1]