MCM520 ← 资料站首页 动态规划 · 深度手册 打开交互阅读器 →

动态规划 · 深度手册

分类：优化类 ｜ 难度：★★★ 高阶 ｜ 编号：dp

📊 数据视角

本资料站收录 343 篇 优秀范文，动态规划共出现约 17 次，排名靠后但重要性高。DP 是解决"具有重叠子问题和最优子结构"问题的标准方法，常与贪心、搜索结合使用。

关键词覆盖："Dynamic Programming"、"DP"、"状态转移"、"备忘录"、"最优子结构"、"区间DP"、"背包DP" 等。

一句话：动态规划是把大问题拆成小问题、存下子问题答案避免重复计算——核心是找"状态"和"转移方程"。

一、这是什么（一句话用途）

有重叠子问题的最优化问题（背包 / 路径 / 序列 / 区间）

二、核心思想

动态规划（Dynamic Programming, DP）适用于具有以下两个性质的问题：

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：递归过程中重复计算相同的子问题

DP 的核心是：定义状态 → 找转移方程 → 确定边界 → 计算顺序。

两种实现方式：

  • 自顶向下（备忘录）：递归 + 缓存已计算结果
  • 自底向上（递推）：从小问题逐步构建到大问题

三、常见 DP 类型

3.1 线性 DP

状态定义：dp[i]dp[i] 表示前 ii 个元素的最优解

问题 状态 转移方程
斐波那契 dp[i]dp[i] dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]
最长上升子序列 LIS dp[i]dp[i] dp[i]=1+max⁡j<i,a[j]<a[i]dp[j]dp[i] = 1 + \max_{j<i, a[j]<a[i]} dp[j]
最大子段和 dp[i]dp[i] dp[i]=max⁡(a[i],dp[i−1]+a[i])dp[i] = \max(a[i], dp[i-1]+a[i])
编辑距离 dp[i][j]dp[i][j] dp[i][j]=min⁡(dp[i][j] = \min( 插入, 删除, 替换 ))

3.2 背包 DP

类型 状态 转移方程
0-1 背包 dp[i][w]dp[i][w] 前 i 个物品，容量 w dp[i][w]=max⁡(dp[i−1][w],dp[i−1][w−wi]+vi)dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i]+v_i)
完全背包 dp[w]dp[w] 容量 w dp[w]=max⁡(dp[w],dp[w−wi]+vi)dp[w] = \max(dp[w], dp[w-w_i]+v_i)
多重背包 dp[i][w]dp[i][w] 限制次数 k

3.3 区间 DP

状态：dp[i][j]dp[i][j] 表示区间 [i,j][i,j] 的最优解

dp[i][j]=min⁡i≤k<j{dp[i][k]+dp[k+1][j]}+cost(i,j)dp[i][j] = \min_{i \le k < j} \{dp[i][k] + dp[k+1][j]\} + cost(i,j)

典型应用：矩阵链乘法、最优二叉搜索树、石子合并。

3.4 树形 DP

在树上进行 DP，通常后序遍历（从叶子到根）：

dp[u][0/1]=以 u 为根，不选/选 u 的最优解dp[u][0/1] = \text{以 u 为根，不选/选 u 的最优解}

典型应用：树的最小顶点覆盖、树上最长路径。

四、Python 实现示例

4.1 0-1 背包问题

def knapsack_01(weights, values, capacity):
    """0-1背包：每个物品只能选一次"""
    n = len(weights)
    # dp[w] = 容量w时的最大价值
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 逆序遍历，确保每个物品只选一次
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

# 测试
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(f"最大价值: {knapsack_01(weights, values, capacity)}")

4.2 最长公共子序列 LCS

def lcs(s1, s2):
    """最长公共子序列"""
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i] 和 s2[:j] 的 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 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])
    
    # 回溯找 LCS
    result = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            result.append(s1[i-1])
            i -= 1; j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    
    return ''.join(reversed(result)), dp[m][n]

s1, s2 = "ABCBDAB", "BDCABA"
seq, length = lcs(s1, s2)
print(f"LCS: {seq}, 长度: {length}")

4.3 最长上升子序列 LIS（O(n log n)）

import bisect

def lis_length(nums):
    """最长上升子序列长度（O(n log n)）"""
    tails = []  # tails[i] = 长度为 i+1 的上升子序列的最小末尾
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

print(f"LIS长度: {lis_length([3, 1, 4, 1, 5, 9, 2, 6])}")  # 5 (1,3,4,5,9)

4.4 矩阵链乘法

def matrix_chain_order(p):
    """矩阵链乘法：最少标量乘法次数"""
    n = len(p) - 1  # n 个矩阵
    # 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] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

# 测试：矩阵维度 [30, 35, 15, 5, 10, 20, 25]
dims = [30, 35, 15, 5, 10, 20, 25]
print(f"最少乘法次数: {matrix_chain_order(dims)}")

五、MATLAB 实现示例

%% 0-1 背包问题（MATLAB/Octave）
weights = [2, 3, 4, 5];
values = [3, 4, 5, 6];
capacity = 8;
n = length(weights);

% dp[w] = 容量w时的最大价值
dp = zeros(1, capacity+1);

for i = 1:n
    for w = capacity:-1:weights(i)
        dp(w) = max(dp(w), dp(w-weights(i)) + values(i));
    end
end

fprintf('最大价值: %d\n', dp(capacity));

六、DP 与贪心的选择

问题特征 推荐方法
具有贪心选择性质 贪心（更快）
子问题重叠且有最优子结构 动态规划
状态空间小 DP 或搜索
状态空间大 贪心或启发式

判断技巧：如果局部最优不能保证全局最优，通常需要用 DP。

七、常见误区与避坑清单

误区 正确做法
状态定义不明确 先想清楚"状态"代表什么
转移方程找错 从小例子手动推导
边界条件遗漏 单独处理空串、单元素等边界
三维以上 DP 没空间优化 观察是否只用上一层，压缩维度
重复计算子问题 用备忘录或自底向上填表

八、论文写作技巧

针对路径优化问题，本文采用动态规划方法。定义状态 dp[i][j]dp[i][j] 为到达第 ii 个城市、剩余燃油量为 jj 时的最小成本。状态转移方程为 dp[i][j]=min⁡k∈pre(i){dp[k][j+wki]+cki}dp[i][j] = \min_{k \in \text{pre}(i)} \{dp[k][j+w_{ki}] + c_{ki}\}，其中 pre(i)\text{pre}(i) 为城市 ii 的前驱城市集合。算法时间复杂度 O(n⋅W)O(n \cdot W)，空间复杂度 O(n⋅W)O(n \cdot W)。

九、相关手册（延伸阅读）

完整算例（数字演示，照着算一遍）

场景：0-1 背包，容量 W=10，物品(重量,价值)：A(2,6)、B(3,10)、C(5,12)、D(7,18)。

DP 表：dp[w]=容量 w 下的最大价值。递推得 dp[10]=28，回溯装包为 B(3,10)+D(7,18)=容量10、价值28。

结论：最优价值 28，由 B、D 组成（A+C+D 超容量、B+C 仅 22）。

十、本手册导航

本手册由「算法深度手册生成器」自动产出。