动态规划的核心理解#

什么是动态规划#

动态规划（DP）的本质是把一个大问题拆成有重叠的子问题，每个子问题只算一次，用数组/哈希表存下来，然后从这些子问题的解推导出原问题的解。

两个核心要素：

最优子结构：大问题的最优解可以由子问题的最优解推导出来
重叠子问题：同一个子问题会被反复遇到，不缓存就会重复计算

简单说：遇到一个问题的状态可以由前面的状态推导出来，而且前面的状态会被多次用到，就该想到 DP。

DP 和递归、记忆化搜索的关系#

三者本质是同一张 DAG（有向无环图）上的不同遍历方式：

1
递归（自顶向下）→ 加 @cache → 记忆化搜索 → 翻转方向 → DP 数组（自底向上）

	方向	存储	典型写法
无缓存递归	顶→底	无	指数级重复计算
记忆化搜索	顶→底	cache/hash	`@cache` + dfs
DP 数组	底→顶	数组	for 循环填表

同一道题，dfs(i) 的参数 i 就是 dp[i] 的下标，返回值就是 dp[i] 的值。记忆化搜索和 DP 数组完全等价，只是遍历方向相反。树形 DP 天然适合递归写法（树没有重叠子问题），线性/网格 DP 适合数组写法（空间压缩更方便）。

什么时候想到动态规划#

题目求最值、方案数、可行性（"最多""最少""有多少种""能不能"）
每个步骤有选择，选择影响后续（选或不选、选哪个）
状态可以用有限个变量描述（位置、容量、剩余次数……）
一看就有大量重复子问题，暴力会超时
数据范围：n ≤ 10^4~10^5（一维 DP），n ≤ 500（二维 DP），n ≤ 20（状态压缩 DP）

反面信号：要你输出所有具体方案（不是方案数）→ 回溯；数据范围 n ≥ 10^6 且无特殊结构 → 贪心或数学。

动态规划五步法#

拿到一道 DP 题按这五步走：

定义 dp 含义：dp[i] 或 dp[i][j] 到底代表什么？一句话说清楚
推导转移方程：当前状态能从哪些前驱状态推导过来？
初始化：基础情况（空串、边界、第一行/列）填什么？
确定遍历顺序：从小到大还是从大到小？外层是什么？保证依赖的前驱先被算好
返回值：最终答案在 dp 数组的哪个位置？

状态定义#

最关键的一步。常见的 dp 含义模式：

以 i 结尾：dp[i] = 以位置 i 结尾时的最优值（LC53 最大子数组和、LC300 LIS）
前 i 个元素：dp[i] = 考虑前 i 个元素时的最优值（LC198 打家劫舍）
区间 [i, j]：dp[i][j] = 区间上的最优值（LC5 回文子串、LC312 戳气球）
双序列：dp[i][j] = s 的前 i 个和 t 的前 j 个的结果（LC1143 LCS、LC72 编辑距离）
状态机：定义多个状态互相转移（股票买卖、LC968 监控二叉树）
mask 压缩：dp[mask] 用二进制表示集合（LC698 划分子集）

好的定义让转移方程自然涌现，坏的定义令人想破头。如果转移很别扭，大概率是状态定义歪了。

状态转移#

从"前一个状态 + 当前选择"推导当前状态。常见模式：

选或不选：dp[i] = max(dp[i-1], dp[i-2] + val[i])（打家劫舍）
选哪个：dp[i] = max(dp[i-1], dp[0..i-1]) + cost（LIS、零钱兑换）
两端收缩：dp[i][j] 由 dp[i+1][j] 和 dp[i][j-1] 转移（回文 DP）
中间切分：dp[i][j] 由 dp[i][k] + dp[k+1][j] 转移（区间 DP）
两路汇合：dp[i][j] 由 dp[i-1][j] 和 dp[i][j-1] 转移（网格路径、LCS）

写不出转移时，画个小例子在纸上手动推三步，看相邻状态之间的关系。

初始化#

初始化决定了"空状态"和"边界状态"的值，直接影响后续所有填表。

0/1 背包：dp[0] = 0（容量 0 时价值 0），其余 -∞ 或 False
计数 DP：dp[0] = 1（"什么都不选"算一种方案）
双序列 DP：dp[i][0] 和 dp[0][j] 对应空串的情况（多开一圈的好处）
路径 DP：第一行和第一列特殊处理（或用越界保护统一）

小技巧：多开一圈（dp = [0] * (n+1)）让 dp[0] 代表空前缀，避免单独处理边界。

遍历顺序#

核心原则：计算 dp[i] 时，它依赖的所有状态必须已经算好。

一维：通常是正序（依赖 i-1），背包倒序（避免物品重复使用）
二维网格：i 正序 j 正序（依赖上方和左方）
回文 DP：i 倒序 j 正序（依赖 i+1 和 j-1）
区间 DP：按区间长度递增（短区间先算）
树形 DP：后序遍历（子节点先算）

不确定顺序时，画一个二维表，标出 (i,j) 依赖哪些格子，箭头方向就是遍历方向。

返回值#

不是所有 DP 的答案都在最后一个位置。常见情况：

dp[n] 或 dp[m][n]：整个问题的答案（LCS、编辑距离）
max(dp)：最优值可能出现在任意位置（最大子数组和、LIS）
dp[0][n-1]：整个区间/字符串的答案（回文 DP、区间 DP）
min(dp[:2])：状态机的最终状态（监控二叉树、股票问题）
dp[(1<<n)-1]：全选状态（状态压缩 DP）

空间压缩#

如果 dp[i] 只依赖固定的前几项，可以用滚动变量代替整个数组：

依赖 dp[i-1] 和 dp[i-2] → 用两个变量（斐波那契、爬楼梯）
依赖 dp[i-1][j] 和 dp[i][j-1] → 用一维数组滚动（二维路径）
依赖上一行的邻近列 → 用两个一维数组交替（下降路径最小和）

空间压缩不是必需的，先写出完整 DP 跑通，再考虑优化。

Python 中常用写法#

Python3 点击展开代码

21 lines 展开代码

# 基础一维 DP
dp = [0] * (n + 1)
for i in range(1, n + 1):
    dp[i] = max(dp[i-1], dp[i-2] + val)

# 多开一圈避免边界判断
dp = [[0] * (n + 1) for _ in range(m + 1)]

# 越界保护（用 INF）
from_up = dp[i-1][j] if i > 0 else float('inf')

# 记忆化搜索（等价 DP）
from functools import cache
@cache
def dfs(i, j):
    ...

# 滚动变量替代数组
cur, prev = 1, 1
for i in range(2, n + 1):
    cur, prev = cur + prev, cur

入门一维 DP#

斐波那契模型#

LC509 - 斐波那契数#

感觉反复写过很多遍了，也罢，放在dp专题里面再写一次吧，注意一下范围问题。

Python3 点击展开代码

9 lines 展开代码

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

LC70 - 爬楼梯#

Python3 点击展开代码

7 lines 展开代码

def climbStairs(self, n: int) -> int:
    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]

LC746 - 使用最小花费爬楼梯#

最小花费爬楼梯问题，我们将dp[i]定义为到i级台阶的最小费用。这里注意，真实台阶的下标是0 ~ n-1，我们求的dp[n]就是已经算上最后的台阶的费用了。

Python3 点击展开代码

6 lines 展开代码

def minCostClimbingStairs(self, cost: list[int]) -> int:
    n = len(cost)
    dp = [0] * (n+1)
    for i in range(2,n+1):
        dp[i] = min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
    return dp[n]

打家劫舍模型#

LC198 - 打家劫舍#

打家劫舍是经典的dp题，也是经典的带限制0-1背包。每个房间可以选择偷或不偷，但是相邻的房子不能被偷。

我们用dp[i]表示偷的房子编号以i结尾的最大金额，其转移方程为 dp[i] = max(dp[i-2]+nums[i], dp[i-1])。它表示要么从两个前偷过来，要么这里不偷沿用上一个的金额。

Python3 点击展开代码

12 lines 展开代码

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

需要注意的就是下标越界问题。所以dp题都应该先考虑让初始条件成立（如果有下标初始化先保证下标有意义），然后再进行转移。

LC213 - 打家劫舍 II#

与打家劫舍的区别是房子现在围成一圈。环形打家劫舍关键限制就是第0间和第n-1间不能同时偷，因为它们相邻。所以合法的方案只能在不偷最后一间，不偷第一间中选。我们直接写出打家劫舍，然后return两种情况的max就行。

Python3 点击展开代码

21 lines 展开代码

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

def rob(self, nums: List[int]) -> int:
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    # 复用打家劫舍1
    return max(self.rob_linear(nums[0 : n - 1]), self.rob_linear(nums[1:n]))

LC337 - 打家劫舍 III#

树形打家劫舍。实际上就是限制父树和子树不能同时被偷。我们复用树的结构，存rob和not_rob两个值，来表示偷/不偷的时候最大金额。这样，就有两个转移方程：

如果偷了当前节点，左右孩子都不能偷了：rob = root.val + left.not_rob + right.not_rob
如果不偷当前节点，那左右孩子可以偷，也可以不偷，各自取最大：not_rob = max(left.rob, left.not_rob) + max(right.rob, right.not_rob)

树形打家劫舍里，当前节点的答案依赖左右子树的答案。所以就是标准的后序问题，按照左右中即可：

Python3 点击展开代码

14 lines 展开代码

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)

        left_rob, left_not_rob = dfs(node.left)
        right_rob, right_not_rob = dfs(node.right)

        rob_cur = node.val + left_not_rob + right_not_rob
        not_rob_cur = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)

        return (rob_cur, not_rob_cur)

    return max(dfs(root))

最大子数组模型#

LC53 - 最大子数组和#

经典dp，注意最大子数组和不一定出现在最后即可。还有注意下标问题，dp最容易出现下标问题，还有边界问题（只有1个数据的时候），尽量脑子里想一下，实在不行就保护0、1、2的时候。

dp[i] 的含义是，是以位置i结尾的时候的最大子数组和。因此dp数组只要开到n-1下标

Python3 点击展开代码

7 lines 展开代码

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

当然，这一题只要求一个最大值，我们可以不维护整个dp数组。我们用curr_max维持遍历的时候目前的最大连续子数组和，然后ans来记录全局答案即可。

Python3 点击展开代码

8 lines 展开代码

def maxSubArray(self, nums: list[int]) -> int:
    n = len(nums)
    curr_max = nums[0]
    ans = nums[0]
    for i in range(1,n):
        curr_max = max(curr_max+nums[i],nums[i])
        ans = max(ans,curr_max)
    return ans

LC918 - 环形子数组的最大和#

环形最大子数组问题可以被拆成两类问题，即最大子数组不跨越首尾、最大子数组跨越首尾。前者回退到LC53，而后者则是可以用总会-最小子数组和。

Python3 点击展开代码

18 lines 展开代码

def maxSubarraySumCircular(nums):
    total = sum(nums)

    cur_max = max_sum = nums[0]
    cur_min = min_sum = nums[0]

    for x in nums[1:]:
        cur_max = max(x, cur_max + x)
        max_sum = max(max_sum, cur_max)

        cur_min = min(x, cur_min + x)
        min_sum = min(min_sum, cur_min)

    # 如果都是负数，也不允许一个都不选。因为可以用 total - min_sum = 0 表示一个都不选。
    if max_sum < 0:
        return max_sum

    return max(max_sum, total - min_sum)

一维 DP 常见模板#

Python3 点击展开代码

13 lines 展开代码

# 基础模板：dp[i] = f(dp[i-1], dp[i-2], ...)
n = len(data)
dp = [0] * n
dp[0] = init_val
for i in range(1, n):
    dp[i] = max(dp[i-1], dp[i-2] + val[i])  # 具体转移看题
return dp[-1]  # 或 max(dp)

# 空间压缩：依赖固定前几项时用两个变量
cur, prev = init_cur, init_prev
for i in range(2, n + 1):
    cur, prev = update(cur, prev), cur
return cur

一维 DP 的核心是搞清楚 dp[i] 代表什么：是以 i 结尾，还是前 i 个元素。

二维网格 DP#

网格路径的核心理解#

网格 DP 的状态依赖上方和左方（或更多方向），典型的转移模式：

1
dp[i][j] = f(dp[i-1][j], dp[i][j-1]) + cost[i][j]

遍历顺序通常是 i 正序 j 正序，保证左和上的状态先算好。

LC62 - 不同路径#

路径题是经典的二维dp。我们用同样尺寸的dp网格，dp[i][j]表示到坐标ij处的路径数，然后返回dp[m-1][n-1]就行。

Python3 点击展开代码

12 lines 展开代码

def uniquePaths(self, m: int, n: int) -> int:
    dp = [[0]* n for _ in range(m)]
    # 初始化边界
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1
    
    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]

LC63 - 不同路径 II#

存在表示为1的石头，不能走。其实就是在石头位置把dp设置为0，这样对后面的路贡献也清掉了。另外边界情况时，如果遇到石头，那后面的也要全部置为0。

Python3 点击展开代码

25 lines 展开代码

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]

    if obstacleGrid[0][0] == 1:
        return 0

    dp[0][0] = 1

    for j in range(1, n):
        if obstacleGrid[0][j] == 0:
            dp[0][j] = dp[0][j - 1]

    for i in range(1, m):
        if obstacleGrid[i][0] == 0:
            dp[i][0] = dp[i - 1][0]

    for i in range(1, m):
        for j in range(1, n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[m - 1][n - 1]

这一题为了简洁，我们也可以不单独拿出来初始化边界，而是在遍历中判断，把石头的dp变成0，其他统一用带边界判断if-else的转移方程（统一规划越界方向0）。

Python3 点击展开代码

19 lines 展开代码

def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [[0] * n for _ in range(m)]

    dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0

    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[i][j] = 0
            # 不单独初始化也要单独弄掉零零
            elif i == 0 and j == 0:
                continue
            else:
                from_up = dp[i - 1][j] if i > 0 else 0
                from_left = dp[i][j - 1] if j > 0 else 0
                dp[i][j] = from_up + from_left

    return dp[-1][-1]

LC64 - 最小路径和#

我们用dp[i][j]存储到当前路径，可以用越界统一正无穷保护。

Python3 点击展开代码

12 lines 展开代码

def minPathSum(self, grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                dp[i][j] = grid[0][0]
            else:
                from_up = dp[i-1][j] if i>0 else float('INF')
                from_left = dp[i][j-1] if j>0 else float('INF')
                dp[i][j] = min(from_left,from_up)+grid[i][j]
    return dp[-1][-1]

LC931 - 下降路径最小和#

下降元素最小和问题，我们可以先用dp[i][j]表示到达坐标ij的下降路径最小和，然后转移方程就是dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + matrix[i][j]，越界保护正无穷即可。

Python3 点击展开代码

13 lines 展开代码

def minFallingPathSum(self, matrix: list[list[int]]) -> int:
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            if i == 0:
                dp[i][j] = matrix[i][j]
            else:
                a = dp[i-1][j-1] if j-1 >= 0 else float('INF')
                b = dp[i-1][j]
                c = dp[i-1][j+1] if j+1 < n else float('INF')
                dp[i][j] = min(a,b,c) + matrix[i][j]
    return min(dp[-1])

LC120 - 三角形最小路径和#

跟上一题差不多的，用dp[i][j]存这里可以走到的最小路径和，j最多只到i+1的位置。转移方程式 dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]。

Python3 点击展开代码

12 lines 展开代码

def minimumTotal(self, triangle: list[list[int]]) -> int:
    n = len(triangle)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1):
            if i == 0:
                dp[i][j] = triangle[i][j]
            else:
                a = dp[i-1][j] if j<=i-1 else float('INF')
                b = dp[i-1][j-1] if j-1>=0 else float('INF')
                dp[i][j] = min(a,b) + triangle[i][j]
    return min(dp[-1])

二维网格 DP 常见模板#

Python3 点击展开代码

20 lines 展开代码

# 基础模板
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
for i in range(1, m): dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n): dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[-1][-1]

# 越界保护版（免去初始化边界）
for i in range(m):
    for j in range(n):
        if i == 0 and j == 0:
            dp[i][j] = grid[0][0]
        else:
            from_up = dp[i-1][j] if i > 0 else float('inf')
            from_left = dp[i][j-1] if j > 0 else float('inf')
            dp[i][j] = min(from_up, from_left) + grid[i][j]

背包 DP#

背包问题的核心理解#

背包问题的本质是：有一个容量限制，每个物品有体积和价值，在不超过容量的前提下做选择，使得总价值最大（或判断能否装满）。

三种基本变体：

0-1 背包：每个物品只能选或不选。遍历时倒序（保证每个物品只用一次）
完全背包：每个物品可以选无数次。遍历时正序（允许同一物品被重复使用）
多重背包：每个物品有有限个。可转化为 0-1 背包或用计数数组优化

此外还有分组背包（每组最多选一个）等变体。

背包 DP 的一个重要技巧是 "求什么就设什么为 dp 值"：

目标	dp 含义	转移核心
最大价值	`dp[j]` = 容量 j 时的最大价值	`dp[j] = max(dp[j], dp[j-v] + w)`
能否装满	`dp[j]` = 能否凑出 j	`dp[j] = dp[j] or dp[j-num]`
装满的方案数	`dp[j]` = 凑出 j 的方案数	`dp[j] += dp[j-num]`
最少物品数	`dp[j]` = 凑出 j 的最少物品数	`dp[j] = min(dp[j], dp[j-num] + 1)`

0-1 背包#

0-1 背包模板#

Python3 点击展开代码

21 lines 展开代码

# 0-1 背包：求最大价值
def knapsack01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for j in range(capacity, weights[i] - 1, -1):  # 倒序！
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[capacity]

# 0-1 背包：能否装满（布尔背包）
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]

# 0-1 背包：方案数
dp = [0] * (target + 1)
dp[0] = 1
for num in nums:
    for j in range(target, num - 1, -1):
        dp[j] += dp[j - num]

倒序是关键——正序会让同一物品被重复使用，变成完全背包。

LC416 - 分割等和子集#

这一题其实就是组合总和 II 的「判定版」，而且 target 固定为总和的一半。完全可以直接拿过来用。

Python3 点击展开代码

22 lines 展开代码

from functools import cache

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        return False

    target = total // 2
    nums.sort()

    @cache
    def dfs(start,target):
        if target<0:
            return False
        if target == 0:
            return True
        
        for i in range(start,len(nums)):
            if dfs(i+1,target-nums[i]):
                return True
        return False
    return dfs(0,target)

但是，如果直接拿过来有一个注意事项，就是组合总和II是需要答案组合，还不能重复，所以有一个跳过下一层选同样数字的设置（那边每个数字只能用一次），这里要去除。然后，那里需要组合的具体数字，这里只需要True/False，有大量重复状态，可以@cache加速。折腾完了之后，你会发现可以惊人打败5%了。。

所以，因为不需要具体选择，只要"能不能凑出来"这个状态的结果，这一题的做法还得是0/1背包滚动更新。0/1 背包解决的是"每个东西只能选一次，在容量/目标限制下选出最优或判断能否达成"的问题。

我们设 dp[j] 为能不能凑出来数字j，不能重复选的0/1背包，做法是倒序遍历，这样能保证每个num只被使用一次。有转移方程 dp[j] = dp[j] or dp[j-num]。

这里有点绕，我们来举个例子理解这个问题。比如[1,5,11,5]，那么我们就要找能不能切分成两个和为11的。首先，我们肯定会让dp[0] = True，因为凑个0默认都是可以凑的，不选呗。然后，我们看到第一个数字1，从大到小更新，按照转移方程，dp[11] = dp[11] or dp[10]，dp[10] = dp[10] or dp[9]…… 这样检查下去，都是False，没有什么影响，直到看到 dp[1] = dp[1] or dp[0] 的时候，dp[1]会被变成True。

你发现了没有，倒序更新不会乱动后面的dp，但是给目前能凑出来的结果dp[j-num]，转移到了dp[j]。如果正序的话，这个结果就会错误被传递下去，一个 dp[0] = True 和一个 num = 1可以直接全部推成True。

至于倒序只到 num-1 比较好理解，因为num不可能凑出来比 num 还小的数字。好了，至此，我们就可以写出这道0/1背包的经典入门题：

Python3 点击展开代码

14 lines 展开代码

def canPartition(nums):
    total = sum(nums)
    if total % 2:
        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]

LC494 - 目标和#

这一题当然可以用带cache的dfs来做，如果想按照01背包来做，需要做一些改动。如果被加号选中的数字为P，减号选中的为N，则有 P-N = target，而且 P + N = S（数组总和），我们可以直接得到 P = (S + target) / 2，问题成功被转化为nums中选一些数让他们和为(S + target) / 2，问有多少选法。

然后，不是求是否能选，而是有多少选法时，转移方程也稍微变一下，变成 dp[j] += dp[j-num] 即可（dp初始化全0）。

Python3 点击展开代码

19 lines 展开代码

def findTargetSumWays(nums, target):
    total = sum(nums)

    if abs(target) > total:
        return 0

    if (total + target) % 2 == 1:
        return 0

    bag = (total + target) // 2

    dp = [0] * (bag + 1)
    dp[0] = 1

    for num in nums:
        for j in range(bag, num - 1, -1):
            dp[j] += dp[j - num]

    return dp[bag]

这样写时间上也是爆杀dfs，不错。

LC1049 - 最后一块石头的重量 II#

这题跟上一题有点像，但是不再提供目标，而是要去求 min(abs(P - N))。两堆谁大谁小无所谓，我们假设 P 小，N - P = (S - P) - P = S - 2P。所以差值最小的情况，就是 P 最接近 S/2 的情况：从 stones 里选一些石头，每个石头最多选一次，让它们的和尽量接近但不超过 sum(stones) // 2。

这就是标准的01背包问题！01背包本来的样子，就是接近但不超过容量要装的最大重量石头。我们按照最大重量背包问题直接求解，转移方程从布尔背包变成了 dp[j] = max(dp[j], dp[j - stone] + stone)。这里就是P最接近 S/2 的重量，然后我们用总重量 - 2P 就达成了。

Python3 点击展开代码

11 lines 展开代码

def lastStoneWeightII(stones):
    total = sum(stones)
    target = total // 2

    dp = [0] * (target + 1)

    for stone in stones:
        for j in range(target, stone - 1, -1):
            dp[j] = max(dp[j], dp[j - stone] + stone)

    return total - 2 * dp[target]

完全背包#

完全背包模板#

Python3 点击展开代码

21 lines 展开代码

# 完全背包：最少硬币数
dp = [INF] * (amount + 1)
dp[0] = 0
for coin in coins:
    for j in range(coin, amount + 1):  # 正序！
        dp[j] = min(dp[j], dp[j - coin] + 1)

# 完全背包：方案数（组合）
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:              # 物品在外
    for j in range(coin, amount + 1):  # 容量在内
        dp[j] += dp[j - coin]

# 排列数：容量在外，物品在内
dp = [0] * (target + 1)
dp[0] = 1
for j in range(1, target + 1):  # 容量在外
    for num in nums:            # 物品在内
        if j >= num:
            dp[j] += dp[j - num]

正序 vs 倒序决定了同一物品能否被多次选取。组合 vs 排列由物品循环和容量循环的嵌套顺序决定。

多重背包#

每个物品有数量限制 count[i]。简单做法是将每个物品拆成 count[i] 个 0-1 背包物品（复杂度过高），优化用二进制拆分或计数数组。

Python3 点击展开代码

12 lines 展开代码

# 多重背包：二进制拆分法
for w, v, cnt in items:
    k = 1
    while k <= cnt:
        # 打包成 k 个物品
        for j in range(capacity, w * k - 1, -1):
            dp[j] = max(dp[j], dp[j - w * k] + v * k)
        cnt -= k
        k *= 2
    if cnt:  # 剩余的再打一包
        for j in range(capacity, w * cnt - 1, -1):
            dp[j] = max(dp[j], dp[j - w * cnt] + v * cnt)

分组背包#

每组物品最多选一个。物品分好组后，外层枚举组，内层倒序枚举容量，最内层枚举组内物品。

Python3 点击展开代码

5 lines 展开代码

for group in groups:
    for j in range(capacity, -1, -1):
        for w, v in group:
            if j >= w:
                dp[j] = max(dp[j], dp[j - w] + v)

背包 DP 遍历顺序总结#

变体	物品循环	容量循环	内层方向	复杂度
0-1 背包	外层	内层	倒序	O(n * C)
完全背包（组合）	外层	内层	正序	O(n * C)
完全背包（排列）	内层	外层	正序	O(n * C)
多重背包	外层（拆分后）	内层	倒序	O(Σcnt * C)
分组背包	外层	内层（中）	倒序	O(G * k * C)

硬币可以选无数次，所以这一题是一个完全背包问题。因此，我们也不需要倒序遍历，直接正序从coin走到底就行。dp[j] 表示凑到 j 所需要的最小硬币数，转移方程 dp[j] = min(dp[j], dp[j-coin] + 1)。初始化dp的时候，用一个很大的数字表示不可达。

Python3 点击展开代码

10 lines 展开代码

def coinChange(self, coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for coin in coins:
        for j in range(coin, amount + 1):
            dp[j] = min(dp[j], dp[j - coin] + 1)

    return dp[amount] if dp[amount] != INF else -1

我们写题的时候一定要先捋清楚dp的含义，这样才知道如何写初始化和转移。

LC518 - 零钱兑换 II#

这一题零钱兑换，依旧无限硬币，但是求的是凑出amount的方案。我们定义dp[j]为凑出j的方案数，显然全部初始化为0。转移方程为 dp[j] += dp[j-coin] 即可。

Python3 点击展开代码

7 lines 展开代码

def change(self, amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for coin in coins:
        for j in range(coin,amount+1):
            dp[j] += dp[j-coin]
    return dp[amount]

LC279 - 完全平方数#

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。这一题实际上也是完全背包，可以选的从1到无限，求最少和数字为n的个数。我们设dp[j]表示凑出j的最小完全平方数个数，转移方程 dp[j] = min(dp[j-i*i]+1,dp[j])。

但是这一题的候选没给有限的数组，我们可以先求出平方小于等于n的最大数字k（这里如果看出来n就是完全平方数那就直接返回1了），然后从1开始试到k。

Python3 点击展开代码

11 lines 展开代码

def numSquares(n: int) -> int:
    INF = n + 1
    dp = [INF] * (n + 1)
    dp[0] = 0

    for i in range(1, int(n ** 0.5) + 1):
        square = i * i
        for j in range(square, n + 1):
            dp[j] = min(dp[j], dp[j - square] + 1)

    return dp[n]

LC377 - 组合总和 IV#

这一题的核心在于"顺序不同算不同方案"，普通的完全背包 dp[j] += dp[j-num] 会默认按照nums顺序调用，无法区分 1+2 和 2+1 。所以，我们要改变格式，将容量放到外层，然后物品放在内层，然后用容量大于物体来判断是否转移：

Python3 点击展开代码

10 lines 展开代码

def combinationSum4(nums, target):
    dp = [0] * (target + 1)
    dp[0] = 1

    for j in range(1, target + 1):
        for num in nums:
            if j >= num:
                dp[j] += dp[j - num]

    return dp[target]

我们注意区分完全背包中的"组合数"和"排列数"，前者物品在外容量在内，后者容量在外物品在内。

多重背包#

分组背包#

背包 DP 遍历顺序总结#

子序列 DP#

子序列 DP 的核心理解#

子序列 DP 处理的是"从序列中按顺序选一部分"的问题。核心区分两个概念：

子数组/子串（Subarray）：必须连续，dp[i] 通常以 i 结尾
子序列（Subsequence）：可以不连续，dp[i] 需要遍历前面所有位置

连续版转移通常只有一种去向（i-1），不连续版需要枚举前驱。

单序列 DP 的 dp[i] 几乎总是"以 i 结尾"的含义。双序列 DP 则是经典 dp[i][j] 二维表。

单序列 DP#

LC300 - 最长递增子序列#

这一题最长递增子序列，特别要注意的是，子序列可以不用连续！设 dp[j] 为到为止j位置的最长递增子序列长度，我们需要遍历前面的i，如果满足nums[i] < nums[j]，则转移 dp[j] = max(dp[j], dp[i] + 1)。

Python3 点击展开代码

10 lines 展开代码

def lengthOfLIS(nums):
    n = len(nums)
    dp = [1] * n

    for j in range(n):
        for i in range(j):
            if nums[i] < nums[j]:
                dp[j] = max(dp[j], dp[i] + 1)

    return max(dp)

当然，这一题有更快的解法，即贪心+二分的方法。

Python3 点击展开代码

20 lines 展开代码

def lengthOfLIS(nums):
    tails = []

    for x in nums:
        left, right = 0, len(tails)

        while left < right:
            mid = (left + right) // 2

            if tails[mid] >= x:
                right = mid
            else:
                left = mid + 1

        if left == len(tails):
            tails.append(x)
        else:
            tails[left] = x

    return len(tails)

LC674 - 最长连续递增序列#

本题和最大连续子数组和相似，都是继续上一个或者另起，我们设 dp[j] 为到j位置为止的最长递增序列，转移方程为：dp[j] = dp[j - 1] + 1 if nums[j - 1] < nums[j] else 1。

Python3 点击展开代码

6 lines 展开代码

def findLengthOfLCIS(self, nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n
    for j in range(1,n):
        dp[j] = dp[j - 1] + 1 if nums[j - 1] < nums[j] else 1
    return max(dp)

然后这一题也同样可以使用两个变量解决：

Python3 点击展开代码

10 lines 展开代码

def findLengthOfLCIS(self, nums: list[int]) -> int:
    cur = 1
    ans = 1
    for j in range(1, len(nums)):
        if nums[j - 1] < nums[j]:
            cur += 1
        else:
            cur = 1
        ans = max(ans, cur)
    return ans

LC32 - 最长有效括号#

同样是dp[i] = 以 i 位置结尾的某种最优结果，但是这一题更复杂一点，属于更复杂的连续结构。有效括号一定会以右括号结尾，所以左括号对应的dp都是0；而当遇到右括号的时候，有两种情况，一种情况是()，这样可以直接把这两个算成有效，然后按照 dp[i-2]+2 来转移就行；另一种情况是))，这样的话，我们需要先找到前一个括号的有效括号长度（即dp[i-1]），然后找到这段有效括号之前的位置即 pre = i - dp[i-1] - 1，如果这个位置大于0且为 ( 则可以配队，转移为 dp[i] += dp[pre-1] if pre>=1 else 0。

Python3 点击展开代码

17 lines 展开代码

def longestValidParentheses(s: str) -> int:
    n = len(s)
    dp = [0] * n
    ans = 0

    for i in range(1, n):
        if s[i] == ')':
            if s[i - 1] == '(':
                dp[i] = 2 + (dp[i - 2] if i >= 2 else 0)
            else:
                pre = i - dp[i - 1] - 1
                if pre >= 0 and s[pre] == '(':
                    dp[i] = dp[i - 1] + 2 + (dp[pre - 1] if pre >= 1 else 0)

            ans = max(ans, dp[i])

    return ans

LC139 - 单词拆分#

判断s能不能拆分成wordDict词表中的单词，一个直观的方法是直接搜索切分。

Python3 点击展开代码

15 lines 展开代码

from functools import cache

def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    wordSet = set(wordDict)
    @cache
    def dfs(start):
        if start == len(s):
            return True
        for end in range(start,len(s)):
            curr = s[start:end+1]
            if curr in wordSet:
                if dfs(end + 1):
                    return True
        return False
    return dfs(0)

加上cache勉强不超时。不过相信也看出来了，这种题目，不要你具体的切分、答案，只问能不能达成状态，搜索一般不是最好的选择。我们可以用dp[j]表示到下标j为止都可以切分，然后思考遍历词表，就有转移方程: dp[j] = dp[j-len(word)] or dp[j] if s[j-len(word)+1+1] in wordSet。（你也看出来了，这样比较变扭，两边都+1，所以我们重新定义状态dp[j]为s[0]能拆分吧，这样dp多一位，式子更好看）： dp[j] = dp[j-len(word)] or dp[j] if s[j-len(word)] in wordSet。

不用wordSet，我们可以把word循环放内部，这样转移方程就进一步简化为了如果 s[j-len(word)] == word 并且 dp[j-len(word)] == True 那么 dp[j] = True。

Python3 点击展开代码

12 lines 展开代码

def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True

    for j in range(1, n + 1):
        for word in wordDict:
            l = len(word)
            if j >= l and dp[j - l] and s[j - l:j] == word:
                dp[j] = True
                break
    return dp[n]

双序列 DP#

LC1143 - 最长公共子序列#

这道题有两个字符串，求他们的最长公共子序列，我们用dp[i][j]表示到text1的i位置和text2的j位置的最长公共子序列，实际上就是我们遍历判断的时候，有两种情况的转移：

当text1[i] == text2[j]，有dp[i][j] = dp[i-1][j-1] + 1
当不相等的时候，可能是i移动也可能是j移动，所以转移为 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

我们多开一圈，让ij表示选中text1和text2的数量，最后返回的dp[m][n]即可：

Python3 点击展开代码

11 lines 展开代码

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    m = len(text1)
    n = 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
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

注意这里我们通过多开一圈，把"空前缀"的基础状态显式放进 dp 表里；它们本来就应该是 0，而数组默认就是 0，所以不用额外初始化。否则，如果直接用i、j表示下标的话，需要自己初始化边界。

所以，要不要多开一圈，请仔细思考初始化。

LC1035 - 不相交的线#

仔细一想，其实就是最长公共子序列的长度啊。演都不演了，直接搬过来就行了：

Python3 点击展开代码

11 lines 展开代码

def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
    m = len(nums1)
    n = len(nums2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if nums1[i-1] == nums2[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[m][n]

LC718 - 最长重复子数组#

这一题是最长公共子序列的连续版（子数组），需要更改转移方程。我们可以借鉴以往的经验，选择dp[i][j]为以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共连续子数组长度，初始化为0。如果nums1[i] == nums2[j]，那么dp[i][j] = dp[i-1][j-1] + 1，一样，但是如果出现 nums1[i] != nums[j]，就要直接归0。很容易理解，如果当前两个数不相等，那以它们结尾的公共连续子数组根本不存在，所以长度只能是 0，而不要求连续的题目中才可能去更新尝试任意一个数组回退一位去寻找最大的。

Python3 点击展开代码

11 lines 展开代码

def findLength(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    ans = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if nums1[i - 1] == nums2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                ans = max(ans, dp[i][j])
    return ans

LC583 - 两个字符串的删除操作#

其实吧，这一题可以直接求最长重复子序列，然后多出来都就是都要删除的。比如我们把LC1143拿过来，然后最后返回一个删除的数目：

Python3 点击展开代码

11 lines 展开代码

def minDistance(self, word1: str, word2: str) -> int:
    m = len(word1)
    n = len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    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] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return m-dp[m][n]+n-dp[m][n]

不过锻炼dp思维，可以重新dp一下。我们用dp[i][j]表示以word1[i-1]和word2[j-1]结尾要想一样需要删除的字符串数目。当两者一样的时候，不用删，也就是dp[i][j] = dp[i-1][j-1]；当两者不一样的时候，可以选择任意一方删除 dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1)。这里最容易想错，你可以理解为当前的dp[i][j]可能是i-1删一个过来或者j-1删一个过来，删就是无条件跳过。

但是这一题需要额外注意的是初始状态，不是全0。当i或j等于0的时候，需要把另外一个删除才行。

Python3 点击展开代码

18 lines 展开代码

def minDistance(self, word1: str, word2: str) -> int:
    m = len(word1)
    n = 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] = min(dp[i-1][j]+1,dp[i][j-1]+1)
    return dp[m][n]

LC72 - 编辑距离#

这一题在上一题上更进一步，有三种选择，我们再次尝试思考一下。初始化跟上一题一样，然后，如果word1[i] == word2[j]，则dp[i][j] = dp[i-1][j-1] 不用操作。如果不一样，可能是三种操作造成的，承接这三种情况的状态，分别是：

插入了一个字符，其实就是相对于word1，word2多走一格，即 dp[i][j] = dp[i][j-1]+1 。比如，abce和abcde，当走到c和d的时候，我们word1插入一个d即可，相对而言，就是都选c的dp加上一步操作即可。
删除了一个字符，也就是上一题的情况，word1多了一个字母，状态就是 dp[i][j] = dp[i-1][j] + 1。
替换一个字符，就是 dp[i][j] = dp[i-1][j-1] + 1，直接替换不一样的结尾。

然后，这三种情况选择一个最小的即可。

Python3 点击展开代码

19 lines 展开代码

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] = min(
                    dp[i-1][j] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1
                )
    return dp[m][n]

LC115 - 不同的子序列#

这一题是给两个字符串s和t，统计s的子序列中t出现的个数。我们可以理解成，通过多少种删除操作，可以让s变成t，注意是只能删s。所以，两个不相等的时候，转移就是删一个s的得到 dp[i][j] = dp[i-1][j]；但是如果两个相等，情况不止是直接从dp[i-1][j-1]转移过来，也可能是删了一个重复相等去删一个s的情况（比如rabbb和rabb的时候，虽然相等，但是可以删一个b让后面t出现），所以转移其实是 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。

删除操作的题目时，如果出现了一样，可以不用管直接从dp[i-1][j-1]转移即可，因为最小删除次数，对保留一对相等字符一定不会多操作。拿rabbb和rabb，就算不删，从这三个b中删除任何一个，都是一次操作，无所谓。但是换成本题，其实有三种删法，也就是答案是3，这就是转移方程差距的来源了。

另外，边界初始化也要更改。当t为空的时候，其实只有一种序列出现在s中，就是空序列，也就是dp[i][0]全1。

Python3 点击展开代码

15 lines 展开代码

def numDistinct(self, s: str, t: str) -> int:
    m = len(s)
    n = len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]

    for i in range(m+1):
        dp[i][0] = 1

    for i in range(1,m+1):
        for j in range(1,n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j]
    return dp[m][n]

子序列 DP 常见模板#

Python3 点击展开代码

21 lines 展开代码

# 单序列不连续（LIS）
dp = [1] * n
for j in range(n):
    for i in range(j):
        if nums[i] < nums[j]:
            dp[j] = max(dp[j], dp[i] + 1)

# 单序列连续（LCIS）
dp = [1] * n
for j in range(1, n):
    if nums[j-1] < nums[j]:
        dp[j] = dp[j-1] + 1

# 双序列（LCS）
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

回文 DP#

回文 DP 的核心理解#

回文 DP 定义一个二维布尔数组 dp[i][j] 表示 s[i:j+1] 是否为回文。转移的核心逻辑是两端字符相等时，向里收缩：

s[i] == s[j] 且 j-i <= 2 → 直接是回文（1~3 个字符）
s[i] == s[j] 且 dp[i+1][j-1] 为真 → 是真回文

遍历顺序是 i 倒序（从右到左）、j 正序（从左到右），因为 dp[i][j] 依赖 dp[i+1][j-1]（更靠里的小区间）。也可以按区间长度递增遍历。

回文子序列不要求连续，不相等时可以跳过一端（和 LCS 类似）。

LC5 - 最长回文子串#

这一题通常有两种解法，一种是中心扩散，一种是二维dp。中心扩散法时，我们定义一个expand函数，然后分奇偶从每个可能的中心开始调用expand，更新为较长的即可。

Python3 点击展开代码

17 lines 展开代码

def longestPalindrome(self, s: str) -> str:
    def expand(i,j)->tuple[int,int]:
        while i>=0 and j<len(s) and s[i] == s[j]:
            i-=1
            j+=1
        return i+1,j-1
    
    start = end = 0

    for i in range(len(s)):
        l1,r1 = expand(i,i)
        l2,r2 = expand(i,i+1)
        if r1 - l1 > end - start:
            start, end = l1, r1
        if r2 - l2 > end - start:
            start, end = l2, r2
    return s[start:end+1]

而这一题的另一种做法，就是二维dp。我们用dp[i][j] = s[i+1] 是否是回文串，如果两端相等，当 j-i<=2 就直接是回文，否则要看里面的 s[i+1] 是否是回文。

Python3 点击展开代码

15 lines 展开代码

def longestPalindrome(s: str) -> str:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start = 0
    max_len = 1

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if j - i + 1 > max_len:
                    start = i
                    max_len = j - i + 1

    return s[start:start + max_len]

这里注意，i是倒序的，因为dp[i][j]依赖dp[i+1][j-1]，所以要先算靠里面的区间。

另外，我们从长度出发，因为两个端点是相互依赖的，所以我们可以循环长度来做。

Python3 点击展开代码

25 lines 展开代码

def longestPalindrome(s: str) -> str:
    # dp[i][j]表示s[i:j+1]是否为回文串
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True

    # 要返回子字符串额外需要的变量
    start = 0
    max_len = 1

    for length in range(2,n+1):
        for i in range(n-length+1):
            j = i + length - 1 
            if s[i] != s[j]:
                dp[i][j] = False
            else:
                if length<=3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]
            # 拿答案
            (start, max_len) = (i, length) if dp[i][j] and length>max_len else (start, max_len)

    return s[start:start+max_len]

LC647 - 回文子串#

这一题，统计回文子串的数目。我们也可以想到用dp来做，同样dp[i][j]表示s[i+1]，每次找到回文子串就+1返回ans即可。

Python3 点击展开代码

12 lines 展开代码

def countSubstrings(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    ans = 0

    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                ans += 1

    return ans

LC516 - 最长回文子序列#

这一题，回文子串变成了回文子序列，也就是说不要求连续了。我们知道，回到非连续的题，我们在不相等的时候，可以选择任意一遍移动继续去寻找，然后取最大/最小。所以这一题，两端不相等的时候，我们去找 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])；而两端相等的时候，直接+2即可。

Python3 点击展开代码

13 lines 展开代码

def longestPalindromeSubseq(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]

这里注意，返回的dp[0][n-1]，也就是整个串。

LC1312 - 让字符串成为回文串的最少插入次数#

同理，这一题的转移不相等的时候可以写成 dp[i][j] = min(dp[i+1][j] + 1, dp[i][j-1] + 1)；相等的话dp[i][j] = dp[i+1][j-1]。（右边插入，等效于和左边往前走一步的dp+1一样结果，比如abcb，插入abcba，新dp等效于bcb+1）

Python3 点击展开代码

12 lines 展开代码

def minInsertions(s: str) -> int:
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1

    return dp[0][n - 1]

回文 DP 常见模板#

Python3 点击展开代码

17 lines 展开代码

# 回文子串/子序列 DP，i 倒序 j 正序
for i in range(n-1, -1, -1):
    for j in range(i, n):
        if s[i] == s[j]:
            if j - i <= 2:
                dp[i][j] = True  # 或 j-i+1 (长度)
            else:
                dp[i][j] = dp[i+1][j-1]  # 或 dp[i+1][j-1] + 2

# 回文子序列（不连续）
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])

股票买卖 DP#

股票 DP 的核心理解#

股票类 DP 统一使用两个核心状态（状态机）：

hold：今天结束后手里有股票，所能达到的最大利润（买入花掉的钱也算进去，所以通常为负或减少）
cash：今天结束后手里没股票，所能达到的最大利润

每天的转移方程只有两个：

1
cash = max(cash, hold + price)        # 不动 vs 卖出
2
hold = max(hold, X - price)           # 不动 vs 买入

所有变体的唯一区别就是买入时用来减的 X 是什么：

题目	X	含义
LC121（限 1 次）	`0`	只能买一次，没有历史利润
LC122（无限次）	`cash`	用累积利润继续买
LC123（限 2 次）	`sell1`	第二次买依赖第一次卖的利润
LC188（限 k 次）	`sell[t-1]`	第 t 次买依赖 t-1 次卖的利润
LC309（冷冻期）	`cash_before_yesterday`	卖出后隔一天才能买
LC714（手续费）	`cash`（同 122）	卖时扣 `fee`

LC121 - 买卖股票的最佳时机#

常规解法是维持当前最小值，算所有点的利润。

Python3 点击展开代码

7 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    min_price = float("INF")
    max_profit = 0
    for price in prices:
        min_price = price if price<min_price else min_price
        max_profit = max(max_profit,price-min_price)
    return max_profit

那么为什么放在dp里面呢，我们可以将dp[j]定义为在j下标的时候可以获得最大的利润，然后我们可以在每个位置从头开始循环到j，找到 prices[i] < prices[j] 之后，用转移 dp[j] = dp[i] + (prices[j]-prices[i]) 更新利润。

Python3 点击展开代码

8 lines 展开代码

def maxProfit(prices: list[int]) -> int:
    n = len(prices)
    dp = [0] * n
    for j in range(1,n):
        for i in range(j):
            if prices[i] < prices[j]:
                dp[j] = max(dp[i] + (prices[j]-prices[i]),dp[j])
    return max(dp)

不过这个法子太朴素所以直接超时了。这里，我们引入通杀股票问题的股票DP，它定义了两个状态，hold 是"如果我今天收盘手里必须有股票，我最多还能剩多少钱"；cash 是"如果我今天收盘手里必须没股票，我最多已经赚多少钱"。其实就是分开算买股票花的钱和卖股票赚的钱，最后去返回cash即可。

那么，第一天的hold，我赚不了钱，利润只能是 -prices[0]，买入第一天的股票。cash收盘也拿不到现金。

我们举个最小例子，比如[7, 1, 5]。初始持股 hold = -7，cash = 0。遇到价格1的时候，先算这一天直接卖出，cash = max(0, -7+1) = 0，显然不合算，然后再更新hold， hold = max(-7, -1) = -1，也就是说，这一天买入比前一天买入好，所以更新hold 为 -1 ；遇到5的时候，cash = max(0, -1 + 5) = 4，说明卖出可得4元，然后再更新 hold = max(-1, -5) = -1，说明还是捏着-1比较好。

Python3 点击展开代码

12 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    hold = -prices[0]
    cash = 0

    for price in prices[1:]:
        new_cash = max(cash, hold + price)
        new_hold = max(hold, -price)

        cash = new_cash
        hold = new_hold

    return cash

LC122 - 买卖股票的最佳时机 II#

买卖股票II允许你在持股一个的情况下，每天都可以多次买卖，最后得到的利润总和要最大。所以，我们在定义的时候，cash可以差不多，都是 cash = max(cash, hold + price)，但是hold不能再简单取最小的买入代价。之前，只能交易一次，如果今天买入，说明之前没有交易，收益为0，所以只能结果是 hold = max(hold, 0-price)；而这一题则是可能有cash了，hold = max(hold, cash - price)。

只需要改变一行。

Python3 点击展开代码

12 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    hold = -prices[0]
    cash = 0

    for price in prices[1:]:
        new_cash = max(cash, hold + price)
        new_hold = max(hold, cash - price)

        cash = new_cash
        hold = new_hold

    return cash

LC123 - 买卖股票的最佳时机 III#

这一题，给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格，且最多只能完成两比交易。所以这一题，我们其实可以看成两个买卖股票I，第二次的buy要承接第一次sell得到的利润，因为不能同时交易，买二必先卖一。

Python3 点击展开代码

16 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    buy1 = -prices[0]
    sell1 = 0
    buy2 = -prices[0]
    sell2 = 0

    for price in prices[1:]:
        new_buy1 = max(buy1, -price)
        new_sell1 = max(sell1, buy1 + price)

        new_buy2 = max(buy2, sell1 - price)
        new_sell2 = max(sell2, buy2 + price)

        buy1, sell1, buy2, sell2 = new_buy1, new_sell1, new_buy2, new_sell2

    return sell2

LC188 - 买卖股票的最佳时机 IV#

这一题再次升级，最多重复买卖k次，但是依然不能同时交易。其实就是将LC123的四个状态推广成循环，变成"buy[1], sell[1], buy[2], sell[2], …, buy[k], sell[k]"。

Python3 点击展开代码

22 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    n = len(prices)
    if n == 0 or k == 0:
        return 0

    buy = [-10**18] * (k + 1)
    sell = [0] * (k + 1)

    for t in range(1, k + 1):
        buy[t] = -prices[0]

    for price in prices[1:]:
        new_buy = buy[:]
        new_sell = sell[:]

        for t in range(1, k + 1):
            new_buy[t] = max(buy[t], sell[t - 1] - price)
            new_sell[t] = max(sell[t], buy[t] + price)

        buy, sell = new_buy, new_sell

    return sell[k]

LC309 - 买卖股票的最佳时机含冷冻期#

这一题给股票买卖带来了冷冻期，卖出股票无法第二天买入。所以，我们的新hold必须要是前天的cash来减。要改的只有这里。

Python3 点击展开代码

16 lines 展开代码

def maxProfit(self, prices: list[int]) -> int:
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]
    cash_before_yesterday = 0
    cash = 0

    for price in prices:
        new_cash = max(cash,hold + price)
        new_hold = max(hold,cash_before_yesterday-price)

        cash_before_yesterday = cash
        cash = new_cash
        hold = new_hold
    return cash

LC714 - 买卖股票的最佳时机含手续费#

这一题和LC122（无限次买卖）相比，只是多了一个手续费，更改一下cash的更新即可解决。

Python3 点击展开代码

14 lines 展开代码

def maxProfit(self, prices: list[int], fee: int) -> int:
    n = len(prices)
    if n == 0:
        return 0
    hold = -prices[0]
    cash = 0

    for price in prices:
        new_cash = max(cash,hold + price - fee)
        new_hold = max(hold,cash - price)

        cash = new_cash
        hold = new_hold
    return cash

股票 DP 常见模板#

Python3 点击展开代码

16 lines 展开代码

# 通用股票模板（LC122 无限次交易）
hold, cash = -prices[0], 0
for price in prices[1:]:
    cash = max(cash, hold + price)      # 卖出
    hold = max(hold, cash - price)      # 买入
return cash

# k 次交易（LC188）
buy = [-inf] * (k+1); sell = [0] * (k+1)
for t in range(1, k+1):
    buy[t] = -prices[0]
for price in prices[1:]:
    for t in range(1, k+1):
        buy[t] = max(buy[t], sell[t-1] - price)
        sell[t] = max(sell[t], buy[t] + price)
return sell[k]

区间 DP#

区间 DP 的核心理解#

区间 DP 的状态定义在 [i, j] 这个区间上，大区间的解通过枚举分割点 k，由两个小区间合并得到：

1
dp[i][j] = min/max(dp[i][k] + dp[k][j] + cost(i,j,k))

遍历顺序：按区间长度从小到大（或 i 倒序 j 正序），确保小区间先算好。

两种常见形式：

两端收缩：dp[i][j] 由 dp[i+1][j] 和 dp[i][j-1] 转移（回文 DP、石子游戏）
中间切分：枚举 k 把 [i,j] 切成两段（戳气球、三角剖分）

LC486 - 预测赢家#

预测赢家在dfs中，是标准的对位dfs解法。我们让双方轮流dfs。

Python3 点击展开代码

14 lines 展开代码

from functools import cache

def predictTheWinner(self, nums: list[int]) -> bool:
    # dfs返回的是第一视角下，能赢对手多少分
    @cache
    def dfs(left:int,right:int)->int:
        if left == right:
            return nums[left]
        # 自己加的分 - 对方能多拿的分
        take_left = nums[left] - dfs(left+1,right)
        take_right = nums[right] - dfs(left,right-1)
        return max(take_left,take_right)
    # 先手(玩家1)优势为正数胜利
    return dfs(0,len(nums)-1)>=0

而既然放在这里，那就是使用区间DP的方法来解决。大区间的解，可以通过小区间解决出来。回文 DP（LC5、LC516）其实也算区间 DP 的特例，典型的区间DP是枚举中间切点转移。

我们可以定义 dp[i][j] 为[i,j]上先手能净胜的分数，那么很容易写出转化方程为 dp[i][j] = nums[i] - dp[i+1][j]（对手拿右边你拿左边）, dp[i][j] = nums[j] - dp[i][j-1]（对手拿左边你拿右边），这两者取最大的。显然，又要i倒序j正序。

Python3 点击展开代码

12 lines 展开代码

def predictTheWinner(self, nums: list[int]) -> bool:
    n = len(nums)
    dp = [[0]*n for _ in range(n)] 

    # 初始化（区间成点初始）
    for i in range(n):
        dp[i][i] = nums[i]

    for i in range(n-2,-1,-1):
        for j in range(i+1,n):
            dp[i][j] = max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
    return dp[0][n-1]>=0

LC877 - 石子游戏#

这一题先手必赢来着，但是我们还是用dp做一下吧。依旧设dp[i][j]为区间[i,j]下Alice能获得的相对优势，对角线初始化一下。

Python3 点击展开代码

10 lines 展开代码

def stoneGame(self, piles: list[int]) -> bool:
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    
    for i in range(n-2,-1,-1):
        for j in range(i+1,n):
            dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
    return dp[0][n-1]>0

LC312 - 戳气球#

如果直接想先去戳哪个气球，很难拆分成子问题。我们将dp[i][j]定义为i、j不戳，中间戳完的收益。显然，区间只剩一个k的时候，左右邻居一定是i和j，得到的收益是nums[i]*nums[k]*nums[j]。

那这又有啥用呢？当然有用，我们可以继续往里面拆分，总会有一个情况只有短区间，k是i、j里面唯一的气球，这样就可以推到外面的了。所以，我们枚举最后一个戳的气球k拆分成两个子问题，转移方程为： dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j])。

然后，我们按照长度从短到长遍历，在固定长度中寻找i、j端点，然后再从其中遍历切割点k，这样就可以做到从里到外覆盖所有情况了。如果你有印象，在最长回文子串的时候我们就这么做过。

Python3 点击展开代码

14 lines 展开代码

def maxCoins(self, nums: list[int]) -> int:
    # 补充哨兵
    vals = [1] + nums + [1]          
    m = len(vals)
    dp = [[0] * m for _ in range(m)]
    for length in range(2, m):
        for i in range(m - length):  
            j = i + length           
            for k in range(i + 1, j): 
                dp[i][j] = max(
                    dp[i][j],
                    dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j]
                )
    return dp[0][m - 1]

这个题当然也可以像之前那样遍历，因为dp[i][k]：k < j，同一次外层 i 循环里 j 是正序的，dp[i][k] 已经算过，而dp[k][j]：k > i，i 倒序，所以 dp[k][j] 在上几轮外层已经算过。只不过这题按照长度更直观，不过还是写一下吧：

Python3 点击展开代码

12 lines 展开代码

def maxCoins(self, nums: list[int]) -> int:
    vals = [1] + nums + [1]
    m = len(vals)
    dp = [[0] * m for _ in range(m)]

    for i in range(m - 1, -1, -1):
        for j in range(i + 2, m):
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                    dp[i][k] + dp[k][j] + vals[i] * vals[k] * vals[j])

    return dp[0][m - 1]

LC1039 - 多边形三角剖分的最低得分#

你有一个凸的 n 边形，其每个顶点都有一个整数值。给定一个整数数组 values ，其中 values[i] 是按顺时针顺序第 i 个顶点的值。

假设将多边形剖分为 n - 2 个三角形。对于每个三角形，该三角形的值是顶点标记的乘积，三角剖分的分数是进行三角剖分后所有 n - 2 个三角形的值之和。

返回多边形进行三角剖分后可以得到的最低分。

我们必须要解释一下这题，不然根本写不好。实际上，这个多边形的三角剖分，可以直接换成选一条(i,j)做底边，然后枚举顶点k组成三角形，最后再把左右两块丢给递归。

我们定义dp[i][j]是切开后选择的底边，然后枚举k作为第三个顶点，那么有单词收益是values[i]*values[k]*values[j]，然后可以继续dp[i][k]+dp[k][j]，直到j-i是2的时候，不用选了只有一种可能。所以，这一题简直是和戳气球一模一样！

Python3 点击展开代码

13 lines 展开代码

def minScoreTriangulation(self, values: list[int]) -> int:
    n = len(values)
    dp = [[0] * n for _ in range(n)]

    for gap in range(2, n):
        for i in range(n - gap):
            j = i + gap
            dp[i][j] = float('inf')
            for k in range(i + 1, j):
                dp[i][j] = min(dp[i][j],
                    dp[i][k] + dp[k][j] + values[i] * values[k] * values[j])

    return dp[0][n - 1]

区间 DP 常见模板#

Python3 点击展开代码

11 lines 展开代码

# 按 gap（j-i）遍历
for gap in range(min_gap, n):
    for i in range(n - gap):
        j = i + gap
        for k in range(i + 1, j):    # 枚举分割点
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost)

# 两端收缩（石子游戏等）
for i in range(n-2, -1, -1):
    for j in range(i+1, n):
        dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])

用 gap = j - i 而非 length 来迭代，可以统一戳气球（开区间）和回文子串（闭区间）的写法，只改 min_gap（1 是闭区间，2 是开区间）。

树形 DP#

树形 DP 的核心理解#

树形 DP 是在树上做 DP——子节点的 DP 值算好后，再算父节点，底层逻辑是后序遍历。和线性 DP 的区别只是：状态依赖的不是 dp[i-1]，而是 dp[left.child] 和 dp[right.child]。

树形 DP 的递归 dfs 返回包含所有必要状态的元组，每个节点根据子节点的返回值计算自己的状态，并更新全局答案。

LC543 - 二叉树的直径#

还是先来复习这一题本来的做法。我们递归让每个结点都有机会做中转点来更新最长直径，然后我们递归的时候为了方便计算直径只返回以这条边为起点的最长长度。

Python3 点击展开代码

13 lines 展开代码

def diameterOfBinaryTree(self, root: TreeNode):
    max_len = 0
    def dfs(node:TreeNode)->int:
        nonlocal max_len
        if not node:
            return 0
        left_len = dfs(node.left)
        right_len = dfs(node.right)
        # 题目要算的是边数
        max_len = max(left_len + right_len, max_len)
        return max(left_len+1,right_len+1)
    dfs(root)
    return max_len

那到底是什么是树形dp？其实啊，树形 DP 就是在树上做 DP（划掉）。就是子节点的 DP 值算好了，再算父节点的。底层的逻辑就是后序遍历。然后这种dfs其实就是树形dp的标准写法了（除非你想从叶子到根一个一个填）。这也得益于树本身没有重叠子问题，不需要cache也不需要dp优化。

LC124 - 二叉树中的最大路径和#

和上一题的区别仅仅在于多了个节点值，相信会了上题也是秒杀的。不过我容易犯错，主要是现在val可能有负数了，加上不一定是正收益，所以我们要即使截断负数（后序的话负数只会作为0传上来）：

Python3 点击展开代码

20 lines 展开代码

class TreeNode:
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

def maxPathSum(self, root: TreeNode) -> int:
    max_val = float('-INF')
    def dfs(node:TreeNode)->int:
        nonlocal max_val
        if not node:
            return 0
        left_val = max(dfs(node.left),0)
        right_val = max(dfs(node.right),0)

        max_val = max(left_val+right_val+node.val,max_val)

        return max(left_val,right_val) + node.val
    dfs(root)
    return max_val

LC968 - 监控二叉树#

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。

这一题是三状态树形dp，被父亲监控、被孩子监控、自己带着监控。

Python3 点击展开代码

26 lines 展开代码

class TreeNode:
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

def minCameraCover(self, root: TreeNode) -> int:
    def dfs(node):
        if not node:
            return float('inf'), 0, 0  # 空节点不可能有摄像头

        l_cam, l_by_child, l_by_parent = dfs(node.left)
        r_cam, r_by_child, r_by_parent = dfs(node.right)

        # 放摄像头：左右孩子爱怎样怎样，我已经全覆盖了
        with_cam = 1 + min(l_cam, l_by_child, l_by_parent) + min(r_cam, r_by_child, r_by_parent)

        # 被孩子覆盖：左右孩子至少有一个放摄像头
        by_child = min(l_cam + min(r_cam, r_by_child),r_cam + min(l_cam, l_by_child))

        # 被父节点覆盖：左右孩子不能指望父节点（父被更上层覆盖），只能靠自己或自己孩子
        by_parent = min(l_cam, l_by_child) + min(r_cam, r_by_child)

        return with_cam, by_child, by_parent
    # 根没有父节点
    return min(dfs(root)[:2])

LC337 - 打家劫舍 III#

打家劫舍III是树形小区，解法也是树形dp。我们让dfs返回这里偷或者不偷的最高收益，每个节点偷或不偷的收益可以用两种转移方程解决，分别是这个偷左右都不偷和这个不偷，左右偷的较大收益。

Python3 点击展开代码

14 lines 展开代码

def rob(self, root: TreeNode) -> int:
    def dfs(node):
        if not node:
            return (0, 0)

        left_rob, left_not_rob = dfs(node.left)
        right_rob, right_not_rob = dfs(node.right)

        rob_cur = node.val + left_not_rob + right_not_rob
        not_rob_cur = max(left_rob, left_not_rob) + max(right_rob, right_not_rob)

        return (rob_cur, not_rob_cur)

    return max(dfs(root))

树形 DP 常见模板#

Python3 点击展开代码

23 lines 展开代码

# 通用树形 DP 框架
ans = 0
def dfs(node):
    nonlocal ans
    if not node:
        return base_case
    left = dfs(node.left)
    right = dfs(node.right)
    ans = max(ans, left + right)      # 用子节点更新全局答案
    return max(left, right) + 1       # 返回当前节点的 DP 值
return ans

# 状态机树形 DP（如 LC968）
def dfs(node):
    if not node:
        return inf, 0, 0  # 空节点不能有摄像头
    l_cam, l_covered, l_not = dfs(node.left)
    r_cam, r_covered, r_not = dfs(node.right)
    cam = 1 + min(l_cam, l_covered, l_not) + min(r_cam, r_covered, r_not)
    covered = min(l_cam + min(r_cam, r_covered), r_cam + min(l_cam, l_covered))
    not_covered = min(l_cam, l_covered) + min(r_cam, r_covered)
    return cam, covered, not_covered
return min(dfs(root)[:2])

树形 DP 天然适合递归写法，树没有重叠子问题，不需要 @cache。

状态压缩 DP#

状态压缩的核心理解#

当 n 很小（≤ 20~25）且决策只关心"哪些元素已经被用了"，可以把选中集合压缩成一个二进制整数 mask。mask 的第 i 位是 1 表示第 i 个元素已被选用。

核心位运算：

1 << n：状态总数（2^n）
1 << i：只有第 i 位为 1 的面具
mask & (1 << i)：检查第 i 位是否为 1（读）
mask | (1 << i)：将第 i 位设为 1（写）
mask.bit_count()：统计 mask 中有多少个 1

LC698 - 划分为 K 个相等的子集#

还记得之前的做法吗，是桶划分。我们要分成k个非空子集，就要去装k个桶。我们先算出k个桶的容积，然后从最大的数开始dfs，放桶，如果第一个都放不下，就没有放的必要了，如果最后放满了桶就成功了。

Python3 点击展开代码

31 lines 展开代码

def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
    total = sum(nums)

    if total % k != 0:
        return False
    
    target = total // k
    nums.sort(reverse=True)

    if nums[0]>target:
        return False
    
    buckets = [0] * k

    def dfs(index:int)->bool:
        if index == len(nums):
            return all(bucket == target for bucket in buckets)
        num = nums[index]
        for i in range(k):
            if buckets[i] + num > target:
                continue
            buckets[i] += num
            if dfs(index+1):
                return True
            buckets[i] -= num

            # 放空桶都失败了直接裁剪
            if buckets[i] == 0:
                return False
        return False
    return dfs(0)

那么，这一题既然放在状态压缩dp，是什么意思呢？回溯法虽然容易理解，但是每次要做两种选择，剪枝能让它不爆炸但绝不是最优。最优的方式是用n个数字的"用没用"编码成n位二进制数mask，比如n=5，用mask = 01001表示第0个和第3个数已经被选了。

此时，用dp[mask]来表示当前正在处理的桶装了多少，就不用维持很多桶了，因为每个桶的容量一样，我们只看当前选择有没有装满，最后只要判断dp[全1]也就是全部都被选了一遍就可以了。（不熟悉位运算的话，mask & (1 << i)是判断第i位是不是1，mask | (1 << i)是将第i位变成1）

Python3 点击展开代码

25 lines 展开代码

def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k

    n = len(nums)
    # dp记录状态为mask下当前桶装了多少
    dp = [-1] * (1 << n)   
    dp[0] = 0
    # 1<<n就是2^n个状态，即每个数字选或不选
    for mask in range(1 << n):
        if dp[mask] == -1:  # 不可达，跳过
            continue
        for i in range(n):
            # 检查第i位是不是1
            if mask & (1 << i):
                continue
            cur = dp[mask] + nums[i]
            if cur > target:
                continue
            # cur == target → cur % target == 0：当前桶刚好满，清零，下一个数字进新桶
            # cur < target → cur % target == cur：当前桶还没满，继续往里装
            dp[mask | (1 << i)] = cur % target
    return dp[(1 << n) - 1] == 0

LC473 - 火柴拼正方形#

还是先用传统桶dfs来做一下。

Python3 点击展开代码

25 lines 展开代码

def makesquare(self, matchsticks: list[int]) -> bool:
    total = sum(matchsticks)
    n = len(matchsticks)
    if total % 4 != 0:
        return False
    target = total // 4
    buckets = [0]*4
    matchsticks.sort(reverse=True)
    def dfs(i):
        if i == n:
            return all(bucket == target for bucket in buckets)
        matchstick = matchsticks[i]
        for k in range(4):
            if buckets[k]+matchstick>target:
                continue
            buckets[k] += matchstick
            if dfs(i+1):
                return True
            buckets[k] -= matchstick

            # 如果空桶放入失败，则肯定失败
            if buckets[k] == 0:
                return False
        return False
    return dfs(0)

@cache 只在状态完全由函数参数决定时安全。有外部可变变量时，缓存键不包含它，等于把不同状态误判成同一个。所以要先用cache，我们需要将桶也编码进去，但是这样状态数爆炸，还不如mask压缩。

我们尝试用上一题的mask压缩。

Python3 点击展开代码

19 lines 展开代码

def makesquare(self, matchsticks: list[int]) -> bool:
    total = sum(matchsticks)
    n = len(matchsticks)
    if total % 4 != 0:
        return False
    target = total // 4
    dp = [-1] * (1<<n)
    dp[0] = 0
    for mask in range(1<<n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if mask & (1<<i):
                continue
            curr = matchsticks[i] + dp[mask]
            if curr > target:
                continue
            dp[mask|(1<<i)] = curr % target
    return dp[(1<<n)-1] == 0

LC464 - 我能赢吗#

两个玩家可以轮流从公共整数池中抽取，不使用重复数字，达到或超过desiredTotal即胜利。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现最佳。

这一题比起维持一个是否选过的数组，更方便的做法是状态压缩，也就是用mask来表示。

Python3 点击展开代码

27 lines 展开代码

from functools import cache

def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
    if desiredTotal == 0:
        return True
    # 加起来数字都超不过
    if (1 + maxChoosableInteger) * maxChoosableInteger // 2 < desiredTotal:
        return False
    @cache
    def dfs(mask: int, total: int) -> bool:
        # 对面已经把 total 减到 ≤0 了
        if total <= 0:
            return False
        for i in range(1, maxChoosableInteger + 1):
            # 按下标减少1
            bit = 1 << (i - 1)
            # 用过了
            if mask & bit:
                continue
            # i大于剩下的total，我赢了
            if i >= total:
                return True
            # 我选 i，轮到对手。对手在新局面里输 → 我赢
            if not dfs(mask | bit, total - i):
                return True
        return False
    return dfs(0, desiredTotal)

当然也可以迭代用dp数组，但是说实话没必要，所以算了。

LC526 - 优美的排列#

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一，该数组就是一个优美的排列：

perm[i] 能够被 i 整除
i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的优美排列的数量。

同样是1-n选一个放在某个下标下，我们可以用压缩工具mask，然后把状态压缩到这个数字中。我们可以将遍历所有位置，如果这个数字能放进当前小标（能被整除或者能整除，取决于大小），就先放进去然后再dfs下一个数字。所以，dfs放mask，并返回满足的数量。

Python3 点击展开代码

18 lines 展开代码

from functools import cache

def countArrangement(self, n: int) -> int:
    @cache
    def dfs(mask: int) -> int:
        # 统计填了多少个1了，+1表示目前要填的位置编号
        pos = mask.bit_count() + 1
        if pos > n:
            return 1
        ans = 0
        for num in range(1, n + 1):
            bit = 1 << (num - 1)
            if mask & bit:
                continue
            if num % pos == 0 or pos % num == 0:
                ans += dfs(mask | bit)
        return ans
    return dfs(0)

状态压缩 DP 常见模板#

Python3 点击展开代码

27 lines 展开代码

# 背包式状态压缩（LC698）
dp = [-1] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    if dp[mask] == -1:
        continue
    for i in range(n):
        if mask & (1 << i):
            continue
        cur = dp[mask] + nums[i]
        if cur > target:
            continue
        dp[mask | (1 << i)] = cur % target
return dp[(1 << n) - 1] == 0

# DFS + cache 式状态压缩（LC464）
@cache
def dfs(mask, total):
    for i in range(1, n + 1):
        bit = 1 << (i - 1)
        if mask & bit:
            continue
        if i >= total:
            return True
        if not dfs(mask | bit, total - i):
            return True
    return False

状态压缩 DP 的 n 上限约 20~25（2^20 ≈ 1M），超过这个范围必须换方法。

计数 DP#

计数 DP 的核心理解#

计数 DP 求的是方案数，而不是最值。核心区别在于初始化：dp[0] = 1（"什么都不选"算一种方案），而不是 dp[0] = 0。转移通常是加法而不是 max/min。

识别信号：题目问"有多少种方法/方案/排列"。

LC62 - 不同路径#

LC62上面也已经解决过了，没什么可以多说的。

LC96 - 不同的二叉搜索树#

实际上，这一题就是求一个卡特兰数。先给个公式法：

Python3 点击展开代码

3 lines 展开代码

import math
def numTrees(self, n: int) -> int:
    return math.comb(2*n,n)//(n+1)

不过，不知道结论的话，还是必须从头计数。我们的做法是枚举根节点的位置，dp[j] = 以 1 为根的方案数 + 以 2 为根的方案数 + … + 以 j 为根的方案数。根选为i的时候，左边i-1个节点都比i小，右边j-i个节点都比i大，左右独立，方案数为 dp[i-1]*dp[j-i]。计数转移为 dp[j] += dp[i-1] * dp[j-i]，注意

Python3 点击展开代码

9 lines 展开代码

def numTrees(self, n: int) -> int:
    dp = [0] * (n + 1)
    # 空树
    dp[0] = 1
    for j in range(1, n + 1):
        for i in range(1, j + 1):
            dp[j] += dp[i - 1] * dp[j - i]

    return dp[n]

LC91 - 解码方法#

1对应A，直到26对应Z，进行了编码。现在要你从字符串数字进行有效解码，且存在可能无法解码的字符串。输出解码的总数。

这一题有点像IP划分，让人联想到dfs的划分问题，实际上，好像也确实可以这么做，只要让dfs的逻辑变成累加就行了。

Python3 点击展开代码

22 lines 展开代码

from functools import cache
def numDecodings(self, s: str) -> int:
    n = len(s)
    def valid(sub: str) -> bool:
        if sub[0] == '0':
            return False
        return 1 <= int(sub) <= 26

    @cache
    def dfs(i: int) -> int:
        if i == n:
            return 1
        if s[i] == '0':
            return 0
        # 不用枚举所有end，最多两位
        # 切 1 位，不是前置零一定有效
        ans = dfs(i + 1)
        # 切 2 位
        if i + 1 < n and valid(s[i:i + 2]):
            ans += dfs(i + 2)
        return ans
    return dfs(0)

LC63 - 不同路径 II#

已做过。

计数 DP 常见模板#

Python3 点击展开代码

7 lines 展开代码

# 计数 DP 通用框架
dp = [0] * (target + 1)
dp[0] = 1  # 什么都不选，一种方案
for item in items:
    for j in range(target, item - 1, -1):  # 0-1 背包倒序
        dp[j] += dp[j - item]                # 加法而非 max
return dp[target]

记忆化搜索与 DP 转换#

自顶向下#

递归从原问题出发，一路分解到最小子问题（base case），返回时沿途填充缓存。写法直觉、容易调试，适合状态定义还不清晰的探索阶段。

Python3 点击展开代码

5 lines 展开代码

@cache
def dfs(state):
    if is_base_case(state):
        return base_value
    return max(dfs(s1), dfs(s2), ...)

自底向上#

从最小的 base case 开始，按依赖顺序（通常是 for 循环）逐格填表，直到原问题的位置。更适合需要空间压缩的场景。

Python3 点击展开代码

5 lines 展开代码

dp = [0] * (n + 1)
dp[0] = base_value
for i in range(1, n + 1):
    dp[i] = max(dp[i-1], dp[i-2] + val)
return dp[n]

递归函数如何改成 DP 数组#

三步转换法：

dfs 的参数 → dp 的下标：dfs(i, j) 对应 dp[i][j]
dfs 的返回值 → dp 的值：dp[i][j] 存的就是 dfs 该返回的东西
递归方向 → 循环：递归是从大到小调用，循环就从小到大填表（依赖方向反过来）

1
dfs(i) = max(dfs(i-1), dfs(i-2) + val)      # 递归
2
dp[i] = max(dp[i-1], dp[i-2] + val)         # DP

什么时候保留记忆化搜索#

状态空间稀疏：很多状态根本不会访问到（如博弈 DP 中的剪枝）
状态转移复杂：难以确定遍历顺序时，递归 + cache 更安全
树形 DP：树天然适合递归，不需要显式填表
面试/博客写题：记忆化搜索通常更短更清晰

什么时候必须转 DP：需要空间压缩、必须严格控制内存（n 很大）、需要显式遍历顺序优化。

动态规划题目的分类判断#

拿到一道新题，按以下顺序判断：

看题目是否有重复子问题#

暴力解是否存在对同一状态反复计算？如果每个子问题只会遇到一次（如树的每个节点），递归就够了，不需要 DP。

看题目是否求最值、方案数、可行性#

最值→ 转移用 max/min，初始化边界值
方案数→ 转移用加法，初始化 dp[0]=1
可行性→ 转移用 or，初始化 dp[0]=True

看状态是否依赖前一个位置#

dp[i] 只由 dp[i-1] 推出 → 一维 DP，可能空间压缩到 O(1)。

看状态是否依赖两个序列#

两个字符串/数组的匹配问题 → dp[i][j] 双序列 DP（LCS、编辑距离）。

看是否是容量选择问题#

给定容量目标，从候选集中选物品 → 背包 DP。判断是 0-1（每物最多一次）还是完全（每物无限次）来决定正序或倒序。

看是否是区间合并问题#

问题在数组的一段区间上操作，结果由子区间合并 → 区间 DP（戳气球、三角剖分）。

看是否可以用状态压缩表示集合#

n 很小（≤ 20），只需要知道"哪些元素被用了" → 状态压缩 DP（mask 位运算）。

动态规划常见模板#

一维 DP 模板#

Python3 点击展开代码

4 lines 展开代码

dp = [0] * n; dp[0] = init
for i in range(1, n):
    dp[i] = max(dp[i-1], dp[i-2] + val[i])
return dp[-1]

二维 DP 模板#

Python3 点击展开代码

8 lines 展开代码

dp = [[0]*n for _ in range(m)]
dp[0][0] = init
for i in range(1, m): dp[i][0] = ...  # 第一列
for j in range(1, n): dp[0][j] = ...  # 第一行
for i in range(1, m):
    for j in range(1, n):
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]
return dp[-1][-1]

0-1 背包模板#

Python3 点击展开代码

5 lines 展开代码

dp = [0] * (C+1)
for w, v in items:
    for j in range(C, w-1, -1):      # 倒序
        dp[j] = max(dp[j], dp[j-w] + v)
return dp[C]

完全背包模板#

Python3 点击展开代码

5 lines 展开代码

dp = [0] * (C+1)
for coin in coins:
    for j in range(coin, C+1):       # 正序
        dp[j] = min(dp[j], dp[j-coin] + 1)
return dp[C]

子序列 DP 模板#

Python3 点击展开代码

8 lines 展开代码

dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
    for j in range(1, n+1):
        if s[i-1] == t[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[m][n]

区间 DP 模板#

Python3 点击展开代码

6 lines 展开代码

for gap in range(min_gap, n):
    for i in range(n - gap):
        j = i + gap
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost)
return dp[0][n-1]

树形 DP 模板#

Python3 点击展开代码

6 lines 展开代码

def dfs(node):
    if not node:
        return base
    l, r = dfs(node.left), dfs(node.right)
    ans = max(ans, combine(l, r, node))
    return max(l, r) + 1

状态压缩 DP 模板#

Python3 点击展开代码

7 lines 展开代码

dp = [-1] * (1 << n); dp[0] = 0
for mask in range(1 << n):
    if dp[mask] == -1: continue
    for i in range(n):
        if mask & (1 << i): continue
        dp[mask | (1 << i)] = transition(dp[mask], nums[i])
return dp[(1 << n) - 1]

动态规划问题总结#

DP 的本质就六个字：拆问题，存结果。不论是一维还是二维，递归还是填表，回溯还是 mask，翻来覆去就是在回答三个问题：

状态是什么？—— 用什么变量能唯一描述一个局面？（dp[i]、dp[i][j]、dp[mask]、树节点）
转移从哪里来？—— 当前状态能从哪些前驱状态一步到达？
答案在哪里？—— 最终要返回的是 dp 表的哪个位置？

DP 没有什么魔力，它就是暴力搜索的缓存优化版。遇到新题，先写出暴力（哪怕是脑子里），找到重复子问题，定义好 dp 含义，剩下的转移、初始化、遍历顺序都可以按模板来。刷够这几十道经典题，分类套路就刻进肌肉记忆了。