动态规划

解题五步法

1. 定义状态：dp[i] 表示什么？
2. 写出状态转移方程：dp[i] 和 dp[i-1] 等之间的关系。
3. 初始化：最小的子问题（边界条件）的值。
4. 确定遍历顺序：一般从小到大，背包问题需注意方向。
5. 确定返回值：dp[n]？dp[n-1]？还是 max(dp)？

---

一、线性 DP

状态沿着一个维度（通常是数组下标）递推。

LC 70. 爬楼梯

70. 爬楼梯（简单）

需要 n 阶到达楼顶，每次可以爬 1 或 2 个台阶，有多少种不同的方法？

1. 状态：dp[i] = 爬到第 i 阶的方法数
2. 转移：dp[i] = dp[i-1] + dp[i-2]
3. 初始化：dp[0] = 1，dp[1] = 1
4. 遍历：从 2 到 n
5. 返回：dp[n]

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1  
    dp[1] = 1  
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] 
    return dp[n]

dp[i] 只依赖 dp[i-1] 和 dp[i-2]，用两个变量滚动即可，空间 $O(1)$。

def climbStairs(n: int) -> int:
    if n <= 1:
        return 1
    prev, curr = 1, 1  # dp[i-2], dp[i-1]
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

LC 53. 最大子数组和

53. 最大子数组和

给定一个整数数组 nums，找出一个具有最大和的连续子数组，返回其最大和。

1. 状态：dp[i] = 以第 i 个数结尾的连续子数组的最大和
2. 转移：dp[i] = max(dp[i-1] + nums[i], nums[i])
3. 初始化：dp[0] = nums[0]
4. 遍历：从 0 到 n-1
5. 返回：max(dp)

def maxSubArray(nums: list[int]) -> int:
    pre, ans = 0, nums[0]
    for x in nums:
        pre = max(pre + x, x)
        ans = max(ans, pre)
    return ans

LC 198. 打家劫舍

198. 打家劫舍

一排房屋，每间有一定现金。相邻房屋装有防盗系统，不能同时闯入。求能偷到的最高金额。

1. 状态：dp[i] = 偷到第 i 间房的最高金额
2. 转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i])
3. 初始化：dp[0] = nums[0]，dp[1] = max(nums[0], nums[1])
4. 遍历：从 2 到 n-1
5. 返回：dp[n-1]

数据范围： 1 <= nums.length <= 100， 0 <= nums[i] <= 400

def rob(nums: list[int]) -> int:
	n = len(nums)
    if n == 1:
        return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
    return dp[n - 1]

---

二、二维 DP

状态涉及两个维度（如网格的行和列）。

LC 62. 不同路径

62. 不同路径

m x n 网格，从左上角走到右下角，每次只能向下或向右走一步，共有多少条不同路径？

1. 状态：dp[i][j] = 从起点到 (i, j) 的路径数
2. 转移：dp[i][j] = dp[i-1][j] + dp[i][j-1] （从上边来 + 从左边来）
3. 初始化：第一行和第一列全为 1
4. 遍历：从上到下、从左到右
5. 返回：dp[m-1][n-1]

def uniquePaths(m: int, n: int) -> int:
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

LC 64. 最小路径和

64. 最小路径和

m x n 网格，每个格子有一个非负整数，找一条从左上角到右下角的路径，使路径上数字之和最小。

1. 状态：dp[i][j] = 从起点到 (i, j) 的最小路径和
2. 转移：dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
3. 初始化：dp[0][0] = grid[0][0]，第一行和第一列累加
4. 遍历：从上到下、从左到右
5. 返回：dp[m-1][n-1]

def minPathSum(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j - 1] + grid[0][j]
    for i in range(1, m):
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
    return dp[m - 1][n - 1]

---

三、字符串 DP

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

LC 72. 编辑距离

72. 编辑距离

把 word1 转换成 word2 所需的最少操作数（插入、删除、替换）。

1. 状态：dp[i][j] = word1 前 i 个字符变成 word2 前 j 个字符的最少操作数
2. 转移：
   • 如果 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（不需要操作）
   • 否则取三种操作的最小值：
     • 插入：dp[i][j-1] + 1
     • 删除：dp[i-1][j] + 1
     • 替换：dp[i-1][j-1] + 1
3. 初始化：dp[i][0] = i（删除 i 个字符），dp[0][j] = j（插入 j 个字符）
4. 遍历：从上到下、从左到右
5. 返回：dp[m][n]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i

        for j in range(n+1):
            dp[0][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]

---

四、背包问题

LC 416. 分割等和子集

416. 分割等和子集（中等）

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

判断能否将数组分成两个和相等的子集。

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

1. 状态：dp[j] = 能否凑出和为 j
2. 转移：dp[j] = dp[j] or dp[j - num]
3. 初始化：dp[0] = True
4. 遍历：外层正序物品，内层倒序容量（0-1 背包）
5. 返回：dp[target]，其中 target = sum // 2

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
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

背包模板速记：

• 0-1 背包：内层倒序遍历容量；
• 完全背包：内层正序遍历容量。

---

六、树形 DP

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

LC 337. 打家劫舍 III

337. 打家劫舍 III（中等）

在二叉树上偷东西，不能同时偷直接相连的两个节点，求能偷到的最高金额。

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

1. 状态：每个节点返回 (不选, 选) 两个值
2. 转移：
   • 不选当前节点：左右子节点可以自由选择，取各自的最大值相加。max(left) + max(right)
   • 选当前节点：左右子节点都不能选，只能取”不选”的值再加上当前节点的值。 left[0] + right[0] + node.val
3. 初始化：空节点返回 (0, 0)
4. 遍历：DFS 后序
5. 返回：max(dfs(root))

def rob(root) -> 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

---

小结

• 线性 DP：状态沿一维递推，核心是「当前元素选或不选」；
• 二维 DP：状态有两个维度，转移通常来自上方和左方；
• 字符串 DP：两串比较，字符相同看左上角，不同看左边和上边；
• 背包问题：0-1 背包倒序遍历，完全背包正序遍历；
• 区间 DP：按区间长度从小到大遍历，枚举分割点；
• 树形 DP：后序遍历，返回多个状态供父节点选择；
• 空间优化：当 dp[i] 只依赖前几项时，用滚动变量或滚动数组降维。