动态规划问题求解：从入门到实战的核心策略与案例拆解

比如求“从A到B的最短路径”，动态规划不会直接算A到B的全部可能，而是先算“到B前一个节点的最短路径”，再以此推导B的最短路径。这种“自底向上”的计算方式，能避免重复计算（比如斐波那契递归中的重复调用），效率比暴力法高得多。

这里要记牢动态规划的3个关键特征：
– 重叠子问题：原问题能拆成多个重复的子问题（比如爬楼梯时，到第n阶的方法数依赖n-1和n-2阶）；
– 最优子结构：子问题的最优解能组合成原问题的最优解（比如最短路径中，到B的最短路径一定是到前一个节点的最短路径加当前边的权重）；
– 无后效性：一旦某状态的解确定，就不会被后续状态的计算影响（比如爬楼梯到第i阶的方法数确定后，计算i+1阶时只用这个结果，不用管i阶是怎么来的）。

如何精准定义状态？

状态定义是动态规划的“地基”——定义错了，后面的推导全白费。分享3个我用了5年的状态定义技巧：

1. 状态要“能描述问题的当前局面”

状态通常用dp[i]或dp[i][j]表示，核心是把“当前的位置/条件”转化为变量。比如：
– 爬楼梯问题：dp[i]表示“到第i阶的总方法数”；
– 背包问题：dp[i][j]表示“用前i个物品装容量j的背包，能获得的最大价值”；
– 路径问题：dp[i][j]表示“到网格(i,j)位置的最短路径长度”。

2. 状态要“包含所有必要的信息”

比如“买卖股票的最佳时机”问题，需要考虑“当前是否持有股票”，所以状态要定义为dp[i][0]（第i天不持有股票的最大利润）和dp[i][1]（第i天持有股票的最大利润）。如果只定义dp[i]为第i天的利润，就会漏掉“是否持有”这个关键信息，导致推导错误。

3. 状态要“可递推”

比如“最长递增子序列（LIS）”问题，状态dp[i]表示“以第i个元素结尾的最长递增子序列长度”——这样才能通过比较nums[i]和nums[j]（j<i）的大小，推导dp[i] = max(dp[j]+1, dp[i])。如果定义dp[i]为“前i个元素的最长递增子序列长度”，就无法递推，因为不知道子序列是否包含第i个元素。

状态转移方程的推导技巧

状态转移方程是动态规划的“引擎”，推导时要抓住“当前状态如何由之前的状态得到”。分享2个通用步骤：

步骤1：分析“最后一步的选择”

比如爬楼梯问题，最后一步要么是从i-1阶跨1步，要么是从i-2阶跨2步——所以dp[i] = dp[i-1] + dp[i-2]。
再比如01背包问题，最后一步要么“选第i个物品”（此时容量要减去物品体积，价值加上物品价值），要么“不选第i个物品”（此时状态和前i-1个物品一样）——所以dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])。

步骤2：验证“边界条件”

边界条件是状态的“初始值”，比如：
– 爬楼梯问题：dp[0] = 1（站在0阶，1种方法），dp[1] = 1（到1阶只有1种方法）；
– 背包问题：dp[0][j] = 0（没有物品，价值为0），dp[i][0] = 0（容量为0，价值为0）。

举个具体例子：计算“斐波那契数列的第n项”（本质是爬楼梯问题的变种），状态转移方程是dp[n] = dp[n-1] + dp[n-2]，边界条件dp[0]=0, dp[1]=1。用Python实现的基础版本：

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

那些能提效的优化策略

动态规划的优化主要集中在空间复杂度和时间复杂度上，分享2个常用的优化技巧：

1. 空间优化：用“滚动数组”或“变量代替数组”

很多时候，dp[i]只依赖dp[i-1]或dp[i-2]，这时可以用变量代替数组，把空间复杂度从O(n)降到O(1)。比如爬楼梯问题的优化版本：

def fib_optimized(n):
    if n == 0:
        return 0
    prev, curr = 0, 1
    for _ in range(2, n+1):
        next_val = prev + curr
        prev, curr = curr, next_val
    return curr

这里用prev和curr代替了数组dp，空间复杂度从O(n)变成了O(1)。

2. 时间优化：用“状态压缩”或“单调队列”

比如“滑动窗口最大值”问题，可以用单调队列优化动态规划的时间复杂度；再比如“最长公共子序列”问题，用滚动数组把空间从O(n*m)降到O(min(n,m))。

用经典案例验证策略有效性

光说不练假把式，用2个经典案例验证上面的策略：

案例1：01背包问题（最常见的动态规划问题）

问题描述：有n个物品，每个物品有重量weight[i]和价值value[i]，背包容量为C，求能装的最大价值。

状态定义：dp[j]表示“容量为j的背包能装的最大价值”（优化后的一维状态，因为dp[i][j]只依赖dp[i-1][j]）。
状态转移方程：dp[j] = max(dp[j], dp[j-weight[i]] + value[i])（逆序遍历j，避免重复选同一个物品）。
代码实现：

def knapsack_01(weight, value, C):
    dp = [0]*(C+1)
    for i in range(len(weight)):
        # 逆序遍历，防止重复选同一物品
        for j in range(C, weight[i]-1, -1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[C]

案例2：完全背包问题（物品可以选多次）

问题描述：和01背包类似，但每个物品可以选任意次。
状态转移差异：完全背包的状态转移是正序遍历j（因为物品可以重复选，正序遍历会让dp[j-weight[i]]已经包含了选当前物品的情况）。
代码实现：

def knapsack_complete(weight, value, C):
    dp = [0]*(C+1)
    for i in range(len(weight)):
        # 正序遍历，允许重复选同一物品
        for j in range(weight[i], C+1):
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    return dp[C]

最后想对你说

动态规划不是“魔法”，而是“有规律的解题框架”——只要掌握“定义状态→推导转移方程→优化→验证”的流程，再难的问题也能拆解得七七八八。

我刚开始学的时候，也会对着“买卖股票”问题抓耳挠腮，但把状态定义成dp[i][0]（不持有）和dp[i][1]（持有）后，突然就通了。所以别害怕“不会”，多拆几个案例，多写几行代码，自然就会了。

如果还有疑问，欢迎在评论区留你遇到的动态规划问题，我帮你拆！