动态规划

知识点概述

动态规划（Dynamic Programming）用于解决具有重叠子问题与最优子结构的问题。

适用条件

动态规划能解决的问题必须满足两个核心条件：

1. 最优子结构：原问题的最优解可以由子问题的最优解推导出来
2. 无后效性：一旦确定了子问题的解，后续推导原问题时，不会再改变子问题的解

两种实现方式

1. 记忆化搜索：自上而下的递归实现，配合缓存
2. 递推：自下而上的迭代实现，配合状态转移方程

常见考点

• 状态定义与转移
• 一维/二维 DP
• 空间优化

入门 DP：爬楼梯

70. 爬楼梯

方法一：记忆化搜索

from functools import cache

def climbStairs(self, n: int) -> int:
    @cache  # 自动记忆化，Python 3.9+
    def dfs(i: int) -> int:
        if i == 0:
            return 1
        if i < 0:
            return 0
        return dfs(i - 1) + dfs(i - 2)
    return dfs(n)

方法二：递推

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

方法三：空间优化

def climbStairs(self, n: int) -> int:
    f0 = f1 = 1
    for i in range(2, n + 1):
        new_f = f0 + f1
        f0, f1 = f1, new_f
    return f1

网格图 DP

1594. 矩阵的最大非负积

def maxProductPath(self, grid: List[List[int]]) -> int:
    mod = 10**9 + 7
    m, n = len(grid), len(grid[0])

    # 关键：需要同时维护到每格的【最大积】和【最小积】
    # 因为负数 × 负数 = 正数：当前格是负数时，"之前的最小积"反而可能产生最大积
    maxgt = [[0] * n for _ in range(m)]   # 到 (i,j) 的最大积
    minlt = [[0] * n for _ in range(m)]   # 到 (i,j) 的最小积

    # 初始化起点与第一行/第一列（只有一条路径可达）
    maxgt[0][0] = minlt[0][0] = grid[0][0]
    for i in range(1, n):                       # 第一行：只能从左边来
        maxgt[0][i] = minlt[0][i] = maxgt[0][i - 1] * grid[0][i]
    for i in range(1, m):                       # 第一列：只能从上面来
        maxgt[i][0] = minlt[i][0] = maxgt[i - 1][0] * grid[i][0]

    for i in range(1, m):
        for j in range(1, n):
            # 当前格 >= 0：最大积 × 正数 = 最大积，最小积 × 正数 = 最小积（方向不变）
            if grid[i][j] >= 0:
                maxgt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]
                minlt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]
            else:
                # 当前格 < 0：乘负数后符号翻转！
                # 最大积 ← 之前的最小积（负负得正）
                maxgt[i][j] = min(minlt[i][j - 1], minlt[i - 1][j]) * grid[i][j]
                # 最小积 ← 之前的最大积
                minlt[i][j] = max(maxgt[i][j - 1], maxgt[i - 1][j]) * grid[i][j]

    return maxgt[m - 1][n - 1] % mod if maxgt[m - 1][n - 1] >= 0 else -1

核心套路：DP 中出现"负数乘法"时，不能只存一维状态（最大值），必须同时维护最大和最小，转移时根据符号切换取法。

0-1 背包

每个物品只能选一次（要么选，要么不选）。

416. 分割等和子集

def canPartition(self, nums: List[int]) -> bool:
    @cache
    def dfs(i: int, j: int) -> bool:
        if i < 0:
            return j == 0
        if j < nums[i]:
            return dfs(i - 1, j)  # 只能不选
        return dfs(i - 1, j - nums[i]) or dfs(i - 1, j)  # 选或不选

    s = sum(nums)
    return s % 2 == 0 and dfs(len(nums) - 1, s // 2)

经典线性 DP：最长公共子序列

1143. 最长公共子序列

def longestCommonSubsequence(self, s: str, t: str) -> int:
    n, m = len(s), len(t)

    @cache
    def dfs(i: int, j: int) -> int:
        if i < 0 or j < 0:
            return 0
        if s[i] == t[j]:
            return dfs(i - 1, j - 1) + 1
        return max(dfs(i - 1, j), dfs(i, j - 1))

    return dfs(n - 1, m - 1)

DP 解题步骤

1. 确定状态：定义 dp[i] 或 dp[i][j] 的含义
2. 确定状态转移方程：找出状态之间的关系
3. 确定初始状态：边界条件
4. 确定遍历顺序：确保计算当前状态时，依赖的状态已经计算过
5. 空间优化（可选）：滚动数组等技巧

常见 DP 类型

类型	状态定义	典型题
线性 DP	dp[i]：以 i 结尾的最优值	最长递增子序列、打家劫舍、爬楼梯
网格 DP	dp[i][j]：走到 (i,j) 的最优值	不同路径、最小路径和、矩阵最大积
区间 DP	dp[i][j]：区间 [i,j] 的最优值	石子合并、最长回文子序列
背包 DP	dp[j]：容量 j 的最优值	0-1 背包、完全背包、分割等和子集
树形 DP	dp[node]：以 node 为根的子树的解	打家劫舍 III、监控二叉树
状态压缩 DP	dp[mask]：用二进制表示集合状态	旅行商问题、子集枚举

大部分 DP 题先判断属于哪种类型，再套用该类型的套路确定状态与转移方向。

---

算法可视化

下面的播放器可以改输入后重跑：把数组换成你自己的， 逐步看每一帧的状态怎么变。注意观察状态量是怎么一步步被覆盖的：爬楼梯只留两个变量（空间优化），而背包要留一整张表 —— 因为容量那一维不能省。背包的内层循环必须倒序，把容量档位调大就能看到重复使用同一件物品的后果。