理解动态规划算法：学习笔记

📋 摘要

🎯 学习目标

📚 核心概念

📖 详细知识脉络

🔍 容易混淆之处

💡 关键示例总结

🔄 对比分析

📝 实践与练习

❓ 复习问题

🚀 进阶方向

📌 学习检查清单

🎯 核心要点总结

动态规划的核心思想

动态规划三要素

第一阶段：爬楼梯问题（一维动态规划）

第二阶段：变化题（递推关系的推广）

第三阶段：0-1背包问题（二维动态规划）

1. 递推公式中项数的确定

2. 基础情况的确定

3. 动态规划表格中的索引混淆

4. 倒推法中的比较逻辑

示例1：爬楼梯（斐波那契数列）

示例2：0-1背包问题

一维DP vs 二维DP

动态规划 vs 递归

练习1：基础爬楼梯

练习2：变化爬楼梯

练习3：简单背包问题

概念理解

问题分析

公式推导

尚未学习的内容

未解决的选择

问题描述

关键思考过程

代码实现

递推公式详解

完整计算表格

问题描述

关键思考

递推公式推导

完整计算过程

结果表格

问题描述

状态定义

递推公式

完整填表过程

最终答案

倒推法还原选择的物品

本文档记录了从零开始学习动态规划算法的完整过程。通过爬楼梯问题引入核心思想，经由变化题深化对递推关系的理解，最后通过0-1背包问题掌握二维动态规划表格的应用。学习过程中包含了对常见错误的纠正、递推公式的推导，以及完整的解题实践。

深入理解动态规划算法的原理，掌握：

动态规划的核心思想与适用场景
从具体问题中抽象出状态定义、递推公式和初始条件
使用动态规划表格解决实际问题
通过倒推法还原最优解的具体方案

把大问题拆成小问题，记住小问题的答案，避免重复计算。

动态规划的本质是递归的记忆化：当前问题的答案可以由前面问题的答案推导出来，通过存储中间结果来避免重复计算。

┌────────────────────────────────────────┐
│  1. 状态定义：dp[i] 或 dp[i][j] 的含义  │
│  2. 递推公式：状态之间的推导关系         │
│  3. 初始条件：最小规模问题的直接答案     │
└────────────────────────────────────────┘

假设要爬 10级台阶，每次可以走 1级或 2级。问：有多少种不同的走法？

分析最后一步：

要走到第10级，只能从第9级跨1级，或者从第8级跨2级
因此：到第10级的走法 = 到第9级的走法 + 到第8级的走法

def climb_stairs(n):
    # 基础情况
    if n == 1:
        return 1  # 只有1种：走1级
    if n == 2:
        return 2  # 有2种：1+1 或 2
    
    # 动态规划：从第3级开始，逐级计算
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]  # 关键公式
    
    return dp[n]

# 测试
print(climb_stairs(10))  # 输出：89

dp[i] = dp[i-1] + dp[i-2]
  ↑         ↑        ↑
第i级    从i-1级   从i-2级
走法数   跨1级上来  跨2级上来

翻译成人话：

走到第 i 级的走法数 = 走到第 i-1 级的走法数 + 走到第 i-2 级的走法数

因为最后一步只有两种可能：

从 i-1 级跨 1级上来
从 i-2 级跨 2级上来

台阶数	走法数	计算过程
1级	1	基础情况
2级	2	基础情况
3级	3	2 + 1
4级	5	3 + 2
5级	8	5 + 3
...	...	...
10级	89	55 + 34

规律： 这就是 斐波那契数列：1, 2, 3, 5, 8, 13, 21, ...

小明要上 5级台阶，每次可以走 1级、2级或3级。问：有多少种不同的走法？

最后一步有几种可能？

从第4级跨1级上来
从第3级跨2级上来
从第2级跨3级上来

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

规律总结： 递推公式的项数 = 最后一步的可能性数量

基础情况：

1级台阶：1种走法 → (1)
2级台阶：2种走法 → (1+1), (2)
3级台阶：4种走法 → (1+1+1), (1+2), (2+1), (3)

逐级计算：

dp[4] = dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7
dp[5] = dp[4] + dp[3] + dp[2] = 7 + 4 + 2 = 13

台阶数	走法数	计算过程
1级	1	基础
2级	2	基础
3级	4	基础
4级	7	4 + 2 + 1
5级	13	7 + 4 + 2

背包最多能装 5kg 的重量。有 4个物品：

物品	重量	价值
A	2kg	3元
B	3kg	4元
C	4kg	5元
D	5kg	6元

规则：

每个物品要么装（1次），要么不装（0次）
不能重复装同一个物品
不能超过背包承重

问题： 怎么装才能得到 最大价值？

dp[i][j] 表示：考虑前 i 个物品，背包容量为 j 时，能获得的最大价值

行 = 物品（A, B, C, D）
列 = 背包容量（0kg, 1kg, 2kg, 3kg, 4kg, 5kg）

对于每个格子 dp[i][j]，有两个选择：

┌─────────────────────────────────────────────┐
│  选择1：不装第i个物品 → dp[i-1][j]          │
│  选择2：装第i个物品 → dp[i-1][j-重量] + 价值  │
│                                             │
│  dp[i][j] = max(选择1, 选择2)               │
└─────────────────────────────────────────────┘

第一行（只考虑物品A：重量2，价值3）

	0kg	1kg	2kg	3kg	4kg	5kg
A	0	0	3	3	3	3

解释：

容量0-1kg：装不下A，价值0
容量2-5kg：能装A，价值3

第二行（考虑物品A和B：重量3，价值4）

	0kg	1kg	2kg	3kg	4kg	5kg
A	0	0	3	3	3	3
A+B	0	0	3	4	4	7

关键位置解释：

3kg：装B（价值4）> 装A（价值3）→ 选4
5kg：装A+B（价值7）> 只装B（价值4）→ 选7

第三行（考虑物品A、B、C：重量4，价值5）

	2kg	3kg	4kg	5kg
A	3	3	3	3
A+B	3	4	4	7
A+B+C	3	4	5	7

关键位置：

4kg：装C（价值5）> 不装C（价值4）→ 选5
5kg：装C（价值5）< 不装C（价值7，即A+B）→ 选7

第四行（考虑全部物品A、B、C、D：重量5，价值6）

关键位置：

5kg：装D（价值6）< 不装D（价值7）→ 选7

最大价值 = 7元

从右下角 dp[4][5] = 7 开始倒推：

位置[4][5] = 7，与位置[3][5]相同
→ 说明没选D ↑

位置[3][5] = 7，与位置[2][5]不同（7≠7？等等，这里需要重新检查）

正确倒推过程：

dp[4][5] = 7（考虑A,B,C,D，容量5）
对比 dp[3][5] = 7（考虑A,B,C，容量5）
值相同 → D没选

dp[3][5] = 7（考虑A,B,C，容量5）
对比 dp[2][5] = 7（考虑A,B，容量5）
值相同 → C没选

dp[2][5] = 7（考虑A,B，容量5）
对比 dp[1][5] = 3（考虑A，容量5）
值不同（7≠3）→ B选了！
跳到 dp[1][5-3] = dp[1][2]

dp[1][2] = 3（考虑A，容量2）
对比 dp[0][2] = 0（考虑无物品，容量2）
值不同（3≠0）→ A选了！
跳到 dp[0][2-2] = dp[0][0]

结论：选 A + B，价值 3 + 4 = 7元 ✅

错误理解： 认为递推公式固定为两项相加

正确理解： 递推公式的项数 = 最后一步的可能性数量

问题类型	最后一步可能	递推公式
每次走1或2级	2种	`dp[i] = dp[i-1] + dp[i-2]`
每次走1、2或3级	3种	`dp[i] = dp[i-1] + dp[i-2] + dp[i-3]`

易错点： 忽略基础情况或基础情况计算错误

正确方法： 从最小的、不可再分的问题开始，直接计算答案

爬楼梯（1或2级）基础情况：

dp[1] = 1（只有1种：走1级）
dp[2] = 2（有2种：1+1 或 2）

爬楼梯（1、2或3级）基础情况：

dp[1] = 1（(1)）
dp[2] = 2（(1+1), (2)）
dp[3] = 4（(1+1+1), (1+2), (2+1), (3)）

易错点： 混淆 dp[i] 与第 i 个物品/第 i 级台阶的对应关系

记忆技巧：

一维DP：dp[i] 通常直接对应"规模为 i 的问题"
二维DP：dp[i][j] 通常对应"前 i 个物品，容量/规模为 j"

易错点： 倒推时比较对象错误

正确逻辑：

如果 dp[i][j] == dp[i-1][j] → 第i个物品没选
如果 dp[i][j] != dp[i-1][j] → 第i个物品选了，跳到 dp[i-1][j-w[i]]

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

时间复杂度： O(n)
空间复杂度： O(n)，可优化至 O(1)

def knapsack(weights, values, capacity):
    n = len(weights)
    # dp[i][j] 表示前i个物品，容量j的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(capacity + 1):
            # 不选第i个物品
            dp[i][j] = dp[i-1][j]
            
            # 选第i个物品（如果装得下）
            if j >= weights[i-1]:
                dp[i][j] = max(dp[i][j], 
                              dp[i-1][j-weights[i-1]] + values[i-1])
    
    return dp[n][capacity]

# 测试
weights = [2, 3, 4, 5]  # A, B, C, D的重量
values = [3, 4, 5, 6]   # A, B, C, D的价值
capacity = 5

print(knapsack(weights, values, capacity))  # 输出：7

时间复杂度： O(n × capacity)
空间复杂度： O(n × capacity)，可优化至 O(capacity)

特征	一维DP	二维DP
状态定义	`dp[i]`	`dp[i][j]`
适用问题	单维度变化的问题	双维度变化的问题
典型例子	爬楼梯、斐波那契	背包问题、最长公共子序列
空间复杂度	O(n) 或 O(1)	O(n×m) 或 O(m)

特征	递归	动态规划
计算方式	自顶向下	自底向上
重复计算	大量重复	无重复（记忆化）
时间复杂度	指数级	多项式级
空间复杂度	栈空间	数组存储

题目： 爬8级台阶，每次走1级或2级，有多少种走法？

提示： 使用 dp[i] = dp[i-1] + dp[i-2]

题目： 爬6级台阶，每次走1级、2级或3级，有多少种走法？

提示： 使用 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

题目： 背包容量4kg，物品如下：

物品	重量	价值
X	1kg	2元
Y	2kg	3元
Z	3kg	5元

求最大价值。

提示： 构建 dp[i][j] 表格，i为物品，j为容量

动态规划的核心思想是什么？
- 答案：把大问题拆成小问题，记住小问题的答案，避免重复计算。
动态规划三要素是什么？
- 答案：状态定义、递推公式、初始条件。
如何确定递推公式中的项数？
- 答案：递推公式的项数等于"最后一步的可能性数量"。

在爬楼梯问题中，为什么 dp[5] = 8 而不是 5？
- 答案：dp[4] = 5，dp[3] = 3，所以 dp[5] = dp[4] + dp[3] = 5 + 3 = 8。容易混淆 dp[4] 和 dp[5] 的值。
在0-1背包问题中，dp[i][j] 表示什么？
- 答案：考虑前 i 个物品，背包容量为 j 时，能获得的最大价值。
如何用倒推法找出背包问题中选择了哪些物品？
- 答案：从右下角开始，如果 dp[i][j] == dp[i-1][j] 说明第 i 个物品没选；如果不等，说明选了，跳到 dp[i-1][j-w[i]]。

如果爬楼梯每次可以走1、2、3或4级，递推公式是什么？
- 答案：dp[i] = dp[i-1] + dp[i-2] + dp[i-3] + dp[i-4]
0-1背包问题的递推公式是什么？
- 答案：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

最长公共子序列（LCS）
- 经典的二维动态规划问题
- 用于比较两个序列的相似度
完全背包问题
- 每个物品可以选无限次
- 与0-1背包的状态转移方程略有不同
空间复杂度优化
- 滚动数组技巧
- 将二维DP优化为一维DP
路径记录与还原
- 如何记录动态规划的决策路径
- 如何输出所有最优解

在学习结束时，提出了三个进阶方向供选择：

A. 再练习一道背包问题巩固
B. 学习动态规划的其他类型（比如最长公共子序列）
C. 了解如何优化背包问题的空间复杂度

此选择尚未做出，等待后续学习继续。

完成本学习后，你应该能够：

解释动态规划的核心思想
识别问题是否适合用动态规划解决
定义状态（一维或二维）
推导递推公式
确定初始条件
正确填写动态规划表格
通过倒推法还原最优解
分析动态规划的时间和空间复杂度

A+B+C+D

动态规划的本质是记忆化：存储子问题的答案，避免重复计算
递推关系是关键：当前状态如何由前面状态推导而来
基础情况是起点：最小规模问题的直接答案
填表顺序很重要：通常从小到大，确保计算当前状态时，所需的前面状态已经计算过
倒推法还原方案：从最终结果反向推导，找出具体的选择路径