第1章：基础概念构建
学习目标
- 理解动态规划的基本思想
- 掌握动态规划的核心概念
- 区分动态规划与其他算法
1.1 生活化比喻：从爬楼梯说起
场景：小明要爬一个10级的楼梯，每次可以跨1级或2级台阶，有多少种不同的爬法？
传统思维：从10级开始，每次尝试1级或2级，画出所有路径（类似树形结构）
动态规划思维： 1. 到达第10级台阶，只能从第8级（跨2级）或第9级（跨1级）过来 2. 所以：到达10级的方法数 = 到达8级的方法数 + 到达9级的方法数 3. 依次类推，从第1、2级开始计算
1.2 动态规划定义与适用场景
定义：动态规划（Dynamic Programming, DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
适用场景： 1. 最优子结构：问题的最优解包含子问题的最优解 2. 重叠子问题：子问题会被重复计算多次 3. 无后效性：当前状态只与之前状态有关，与之后状态无关
1.3 核心概念详解
| 概念 | 含义 | 爬楼梯例子 |
|---|---|---|
| 状态 | 描述问题当前情况的信息 | dp[i]表示到达第i级台阶的方法数 |
| 状态转移方程 | 状态之间的关系式 | dp[i] = dp[i-1] + dp[i-2] |
| 边界条件 | 最简单情况的解 | dp[0]=1, dp[1]=1 |
| 最优子结构 | 大问题最优解依赖小问题最优解 | 到10级最优解依赖到8、9级最优解 |
| 重叠子问题 | 子问题被重复计算 | 计算dp[8]时需dp[6]，计算dp[9]时也需dp[6] |
1.4 与递归、贪心算法的区别
// 递归解法（低效）
int fib_recursive(int n) {
if (n <= 1) return n;
return fib_recursive(n-1) + fib_recursive(n-2); // 大量重复计算
}
// 动态规划解法（高效）
int fib_dp(int n) {
vector<int> dp(n+1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 存储结果，避免重复计算
}
return dp[n];
}
// 贪心算法示例（局部最优）
// 找零钱问题中，贪心可能得不到最优解
// 如硬币面值[1, 3, 4]，找6元：贪心选4+1+1（3枚），最优是3+3（2枚）
重点回顾
- 动态规划通过保存子问题结果避免重复计算
- 识别最优子结构和重叠子问题是使用DP的关键
- DP与递归关系密切，但DP更高效
第2章：解题方法论
学习目标
- 掌握动态规划的标准解题步骤
- 学会定义合适的状态
- 能够推导状态转移方程
2.1 动态规划四步法
第一步：判断是否适用动态规划 1. 问题能否分解为子问题？ 2. 子问题是否重叠？ 3. 是否具有最优子结构？
第二步：定义状态 - 原则1（简洁性）：状态应尽可能简单，通常用1-3个维度 - 原则2（无后效性）：当前状态值确定后，后续决策不受之前决策影响 - 原则3（可转移）：状态之间应能建立转移关系
第三步：推导状态转移方程 1. 从最简单情况开始（如n=1,2） 2. 思考如何从已知状态得到新状态 3. 用数学公式表示这种关系
第四步：实现与优化 1. 确定边界条件（最小子问题的解） 2. 选择实现方式（自顶向下/自底向上） 3. 考虑空间优化
2.2 状态定义技巧
| 问题类型 | 状态定义常见形式 | 示例 |
|---|---|---|
| 线性问题 | dp[i] 表示前i个元素的结果 | 最大子数组和 |
| 序列问题 | dp[i] 表示以第i个元素结尾的结果 | 最长递增子序列 |
| 背包问题 | dp[i][j] 表示前i个物品，容量为j时的最优值 | 0-1背包 |
| 字符串问题 | dp[i][j] 表示字符串1前i个字符和字符串2前j个字符的关系 | 编辑距离 |
2.3 两种实现方式对比
// 方式1：自顶向下（记忆化搜索）
int climbStairs_memo(int n, vector<int>& memo) {
if (n <= 1) return 1;
if (memo[n] != -1) return memo[n]; // 已计算过，直接返回
memo[n] = climbStairs_memo(n-1, memo) + climbStairs_memo(n-2, memo);
return memo[n];
}
// 方式2：自底向上（迭代）
int climbStairs_iterative(int n) {
if (n <= 1) return 1;
vector<int> dp(n+1);
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
重点回顾
- 判断→定义→推导→实现 是DP解题的标准流程
- 状态定义要满足简洁性、无后效性、可转移性
- 自顶向下适合思考，自底向上效率更高
第3章：分级例题体系
入门级（1-2星难度）
例题1：斐波那契数列优化
问题描述：求斐波那契数列第n项（n≤1000）
#include <iostream>
#include <vector>
using namespace std;
// 方法1：朴素递归（时间复杂度O(2^n)，不可接受）
int fib_naive(int n) {
if (n <= 1) return n;
return fib_naive(n-1) + fib_naive(n-2);
}
// 方法2：动态规划（时间复杂度O(n)）
int fib_dp(int n) {
if (n <= 1) return n;
// dp[i]表示斐波那契数列第i项的值
vector<int> dp(n+1);
// 边界条件
dp[0] = 0;
dp[1] = 1;
// 状态转移：当前项等于前两项之和
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// 方法3：动态规划+空间优化（只保存前两项）
int fib_optimized(int n) {
if (n <= 1) return n;
int prev1 = 0; // dp[i-2]
int prev2 = 1; // dp[i-1]
int current; // dp[i]
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev1 = prev2;
prev2 = current;
}
return current;
}
int main() {
int n = 10;
cout << "斐波那契数列第" << n << "项：" << endl;
cout << "动态规划解法: " << fib_dp(n) << endl;
cout << "空间优化解法: " << fib_optimized(n) << endl;
return 0;
}
复杂度分析： - 时间复杂度：O(n) - 空间复杂度：O(n) 或 O(1)（优化后）
例题2：爬楼梯问题
问题描述：楼梯有n阶，每次可以爬1阶或2阶，求有多少种不同的方法爬到楼顶
#include <iostream>
#include <vector>
using namespace std;
int climbStairs(int n) {
if (n <= 1) return 1;
// dp[i]表示爬到第i阶楼梯的方法数
vector<int> dp(n+1);
// 边界条件：爬到第0阶有1种方法（不动），第1阶有1种方法
dp[0] = 1;
dp[1] = 1;
// 状态转移：爬到第i阶可以从第i-1阶爬1阶，或从第i-2阶爬2阶
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
// 拓展：如果每次可以爬1阶、2阶或3阶呢？
int climbStairsExtended(int n) {
if (n <= 1) return 1;
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
// 注意：当i>=2时，可以从i-1、i-2、i-3过来
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
if (i >= 3) {
dp[i] += dp[i-3];
}
}
return dp[n];
}
int main() {
int n = 5;
cout << "爬" << n << "阶楼梯的方法数（每次1或2阶）: " << climbStairs(n) << endl;
cout << "爬" << n << "阶楼梯的方法数（每次1、2或3阶）: " << climbStairsExtended(n) << endl;
return 0;
}
例题3：最大子数组和
问题描述：给定一个整数数组，找出连续子数组的最大和
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
// dp[i]表示以第i个元素结尾的最大子数组和
vector<int> dp(n);
// 边界条件：第一个元素的最大子数组和就是它自己
dp[0] = nums[0];
// 初始化最大和为第一个元素
int max_sum = dp[0];
// 状态转移：
// 如果dp[i-1] > 0，那么dp[i] = dp[i-1] + nums[i]
// 如果dp[i-1] <= 0，那么dp[i] = nums[i]（重新开始）
for (int i = 1; i < n; i++) {
if (dp[i-1] > 0) {
dp[i] = dp[i-1] + nums[i];
} else {
dp[i] = nums[i];
}
// 更新最大和
max_sum = max(max_sum, dp[i]);
}
return max_sum;
}
// 空间优化版本
int maxSubArrayOptimized(vector<int>& nums) {
if (nums.empty()) return 0;
int current_sum = nums[0]; // 当前子数组和
int max_sum = nums[0]; // 最大子数组和
for (int i = 1; i < nums.size(); i++) {
// 如果当前和小于0，重新开始计算
if (current_sum < 0) {
current_sum = nums[i];
} else {
current_sum += nums[i];
}
max_sum = max(max_sum, current_sum);
}
return max_sum;
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << "最大子数组和: " << maxSubArray(nums) << endl;
cout << "最大子数组和(优化版): " << maxSubArrayOptimized(nums) << endl;
return 0;
}
状态转移可视化：
数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
dp[i]: [-2, 1, -2, 4, 3, 5, 6, 1, 5]
↑
最大和为6 (4 + -1 + 2 + 1)
进阶级（3-4星难度）
例题4：最长递增子序列
问题描述：给定一个整数数组，找到其中最长的严格递增子序列的长度
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
// dp[i]表示以nums[i]结尾的最长递增子序列长度
vector<int> dp(n, 1); // 每个元素至少可以单独成为子序列
// 记录最长递增子序列的长度
int max_length = 1;
// 状态转移：对于每个i，检查所有j < i
// 如果nums[i] > nums[j]，那么dp[i] = max(dp[i], dp[j] + 1)
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_length = max(max_length, dp[i]);
}
return max_length;
}
// 拓展：输出最长递增子序列本身
vector<int> findLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 1);
vector<int> prev(n, -1); // 记录前驱元素索引
int max_len = 1;
int max_idx = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > max_len) {
max_len = dp[i];
max_idx = i;
}
}
// 根据prev数组重建LIS
vector<int> lis;
int idx = max_idx;
while (idx != -1) {
lis.push_back(nums[idx]);
idx = prev[idx];
}
reverse(lis.begin(), lis.end());
return lis;
}
int main() {
vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
cout << "最长递增子序列长度: " << lengthOfLIS(nums) << endl;
vector<int> lis = findLIS(nums);
cout << "最长递增子序列: ";
for (int num : lis) {
cout << num << " ";
}
cout << endl;
return 0;
}
时间复杂度分析： - 时间复杂度：O(n²)（双重循环） - 空间复杂度：O(n)
例题5：0-1背包问题
问题描述：有n个物品，第i个物品重量为weight[i]，价值为value[i]，背包容量为capacity，求能装入背包的最大价值
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int knapsack01(int capacity, vector<int>& weight, vector<int>& value) {
int n = weight.size();
if (n == 0 || capacity == 0) return 0;
// dp[i][j]表示前i个物品，背包容量为j时的最大价值
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// 初始化：没有物品或容量为0时，价值为0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int j = 0; j <= capacity; j++) {
dp[0][j] = 0;
}
// 状态转移
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
// 情况1：不放入第i个物品
dp[i][j] = dp[i-1][j];
// 情况2：放入第i个物品（前提：容量足够）
if (j >= weight[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][capacity];
}
// 空间优化版本（一维数组）
int knapsack01_optimized(int capacity, vector<int>& weight, vector<int>& value) {
int n = weight.size();
if (n == 0 || capacity == 0) return 0;
// dp[j]表示背包容量为j时的最大价值
vector<int> dp(capacity + 1, 0);
// 注意：这里需要从后向前遍历，确保每个物品只被使用一次
for (int i = 0; i < n; i++) {
for (int j = capacity; j >= weight[i]; j--) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[capacity];
}
// 拓展：输出选择了哪些物品
void knapsackWithTrace(int capacity, vector<int>& weight, vector<int>& value) {
int n = weight.size();
vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
// 计算dp表
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= capacity; j++) {
dp[i][j] = dp[i-1][j];
if (j >= weight[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i-1]] + value[i-1]);
}
}
}
// 回溯找出选择的物品
cout << "最大价值: " << dp[n][capacity] << endl;
cout << "选择的物品: ";
int j = capacity;
for (int i = n; i > 0; i--) {
if (dp[i][j] != dp[i-1][j]) {
cout << i << "号物品 ";
j -= weight[i-1];
}
}
cout << endl;
}
int main() {
int capacity = 10;
vector<int> weight = {2, 3, 4, 5};
vector<int> value = {3, 4, 5, 6};
cout << "0-1背包问题最大价值: " << knapsack01(capacity, weight, value) << endl;
cout << "0-1背包问题最大价值(优化版): " << knapsack01_optimized(capacity, weight, value) << endl;
knapsackWithTrace(capacity, weight, value);
return 0;
}
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) // j >= weight[i]
dp[i][j] = dp[i-1][j] // j < weight[i]
例题6：零钱兑换（最少硬币数）
问题描述：给定不同面额的硬币coins和一个总金额amount，计算凑成总金额所需的最少硬币数
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
// dp[i]表示凑成金额i所需的最少硬币数
vector<int> dp(amount + 1, INT_MAX - 1); // 初始化为一个较大的值
// 边界条件：凑成金额0需要0个硬币
dp[0] = 0;
// 状态转移：对于每个金额i，尝试使用每种硬币
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果dp[amount]还是初始值，说明无法凑出
return dp[amount] == INT_MAX - 1 ? -1 : dp[amount];
}
// 拓展：计算凑成总金额的组合数
int coinChangeWays(vector<int>& coins, int amount) {
// dp[i]表示凑成金额i的组合数
vector<int> dp(amount + 1, 0);
// 边界条件：凑成金额0有1种方式（什么都不选）
dp[0] = 1;
// 注意：这里是先遍历硬币，再遍历金额，确保组合不重复
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
cout << "凑成" << amount << "元需要的最少硬币数: " << coinChange(coins, amount) << endl;
cout << "凑成" << amount << "元的组合数: " << coinChangeWays(coins, amount) << endl;
return 0;
}
关键点： - 初始化dp[0] = 0（金额0需要0个硬币） - dp数组初始化为较大值（表示无法凑出） - 对于每个金额，尝试所有硬币，取最小值
提高级（4-5星难度）
例题7：完全背包问题
问题描述：与0-1背包类似，但每种物品有无限个
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int completeKnapsack(int capacity, vector<int>& weight, vector<int>& value) {
int n = weight.size();
// dp[j]表示背包容量为j时的最大价值
vector<int> dp(capacity + 1, 0);
// 完全背包：从前向后遍历，这样物品可以被重复选择
for (int i = 0; i < n; i++) {
for (int j = weight[i]; j <= capacity; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[capacity];
}
// 拓展：混合背包问题（有些物品有限，有些无限）
int mixedKnapsack(int capacity, vector<int>& weight, vector<int>& value, vector<int>& quantity) {
int n = weight.size();
vector<int> dp(capacity + 1, 0);
for (int i = 0; i < n; i++) {
if (quantity[i] == 0) { // 完全背包（无限个）
for (int j = weight[i]; j <= capacity; j++) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
} else { // 多重背包（有限个）
// 将有限物品转换为0-1背包问题
int k = 1;
int remaining = quantity[i];
while (remaining > 0) {
int take = min(k, remaining);
int w = take * weight[i];
int v = take * value[i];
for (int j = capacity; j >= w; j--) {
dp[j] = max(dp[j], dp[j - w] + v);
}
remaining -= take;
k *= 2;
}
}
}
return dp[capacity];
}
int main() {
int capacity = 10;
vector<int> weight = {2, 3, 4};
vector<int> value = {3, 4, 5};
cout << "完全背包最大价值: " << completeKnapsack(capacity, weight, value) << endl;
// 混合背包示例
vector<int> quantity = {0, 2, 1}; // 0表示无限个，其他数字表示有限个数
cout << "混合背包最大价值: " << mixedKnapsack(capacity, weight, value, quantity) << endl;
return 0;
}
完全背包与0-1背包区别： - 0-1背包：内层循环从后向前遍历，确保物品只选一次 - 完全背包：内层循环从前向后遍历，允许物品重复选择
例题8：编辑距离
问题描述：给定两个单词word1和word2，计算将word1转换成word2所需的最少操作数。操作包括：插入、删除、替换一个字符
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int minDistance(string word1, string word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最少操作数
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 边界条件初始化
// 空字符串转换为空字符串需要0步
// 空字符串转换为长度为j的字符串需要j步插入
// 长度为i的字符串转换为空字符串需要i步删除
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // word1前i个字符转换为空字符串，需要i次删除
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // 空字符串转换为word2前j个字符，需要j次插入
}
// 状态转移
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
// 字符相同，不需要操作
dp[i][j] = dp[i-1][j-1];
} else {
// 字符不同，取三种操作的最小值
// 1. 删除：dp[i-1][j] + 1
// 2. 插入：dp[i][j-1] + 1
// 3. 替换：dp[i-1][j-1] + 1
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
}
}
}
return dp[m][n];
}
// 空间优化版本（使用两行数组）
int minDistanceOptimized(string word1, string word2) {
int m = word1.length();
int n = word2.length();
vector<int> prev(n + 1, 0);
vector<int> curr(n + 1, 0);
// 初始化第一行
for (int j = 0; j <= n; j++) {
prev[j] = j;
}
for (int i = 1; i <= m; i++) {
curr[0] = i; // 当前行的第一列
for (int j = 1; j <= n; j++) {
if (word1[i-1] == word2[j-1]) {
curr[j] = prev[j-1];
} else {
curr[j] = min({prev[j], curr[j-1], prev[j-1]}) + 1;
}
}
prev = curr;
}
return prev[n];
}
int main() {
string word1 = "horse";
string word2 = "ros";
cout << "将\"" << word1 << "\"转换为\"" << word2 << "\"的编辑距离: " << endl;
cout << "标准解法: " << minDistance(word1, word2) << endl;
cout << "优化解法: " << minDistanceOptimized(word1, word2) << endl;
return 0;
}
编辑距离状态转移方程：
如果 word1[i] == word2[j]:
dp[i][j] = dp[i-1][j-1]
否则:
dp[i][j] = min(dp[i-1][j], // 删除
dp[i][j-1], // 插入
dp[i-1][j-1]) // 替换
+ 1
例题9：最长公共子序列
问题描述：给定两个字符串，找到它们的最长公共子序列（LCS）的长度
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int longestCommonSubsequence(string text1, string text2) {
int m = text1.length();
int n = text2.length();
// dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 状态转移
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i-1] == text2[j-1]) {
// 字符相同，LCS长度加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];
}
// 拓展：输出最长公共子序列
string findLCS(string text1, string text2) {
int m = text1.length();
int n = text2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 计算dp表
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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]);
}
}
}
// 回溯重建LCS
string lcs = "";
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1[i-1] == text2[j-1]) {
lcs = text1[i-1] + lcs;
i--;
j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
return lcs;
}
int main() {
string text1 = "abcde";
string text2 = "ace";
cout << "最长公共子序列长度: " << longestCommonSubsequence(text1, text2) << endl;
cout << "最长公共子序列: " << findLCS(text1, text2) << endl;
return 0;
}
LCS与最长公共子串的区别： - 子序列：可以不连续（如"ace"是"abcde"的子序列） - 子串：必须连续（如"bcd"是"abcde"的子串）
第4章：学习效果强化
4.1 综合练习题
练习题1：三角形最小路径和
问题描述：给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
输入三角形示例：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
最小路径和：2 + 3 + 5 + 1 = 11
提示： 1. 状态定义：dp[i][j]表示到达第i行第j列的最小路径和 2. 状态转移：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j] 3. 注意边界条件（第一列和最后一列）
练习题2：打家劫舍
问题描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，但相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例：
输入：[1,2,3,1]
输出：4
解释：偷窃1号房屋（金额=1），然后偷窃3号房屋（金额=3）
提示： 1. 状态定义：dp[i]表示偷窃前i个房屋能获得的最大金额 2. 状态转移：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 3. 边界条件：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
练习题3：不同路径
问题描述：一个机器人位于一个m×n网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
示例：m=3, n=2
输出：3
解释：
从左上角到右下角一共有3条路径：
1. 右→右→下
2. 右→下→右
3. 下→右→右
提示： 1. 状态定义：dp[i][j]表示到达(i,j)格子的路径数 2. 状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1] 3. 边界条件：第一行和第一列都只有1种走法
4.2 常见错误类型及避坑指南
| 错误类型 | 示例 | 正确做法 |
|---|---|---|
| 状态定义不当 | 用dp[i]表示前i个元素的最优解，但无法处理某些约束 | 增加维度，如dp[i][j] |
| 边界条件错误 | 忘记初始化dp[0]或dp[1] | 仔细分析最小子问题的解 |
| 状态转移遗漏 | 只考虑一种情况，忽略其他可能 | 列出所有可能情况，取最优 |
| 空间复杂度高 | 使用二维数组但可以优化为一维 | 分析状态依赖，压缩空间 |
| 循环顺序错误 | 完全背包用了0-1背包的遍历顺序 | 理解问题本质，选择正确顺序 |
4.3 动态规划解题模板
// 动态规划通用模板
int solveDP(问题参数) {
// 1. 特殊情况处理
if (特殊情况) return 结果;
// 2. 定义状态数组
vector<int> dp(大小, 初始值);
// 3. 初始化边界条件
dp[0] = 初始值1;
// 其他边界条件...
// 4. 状态转移
for (int i = 开始; i <= 结束; i++) {
// 根据状态转移方程更新dp[i]
dp[i] = 转移方程;
}
// 5. 返回结果
return dp[目标];
}
第5章：总结与拓展
5.1 动态规划知识体系
动态规划
├── 线性DP
│ ├── 一维：斐波那契、爬楼梯
│ └── 二维：编辑距离、LCS
├── 区间DP
│ ├── 矩阵链乘法
│ └── 石子合并
├── 背包DP
│ ├── 0-1背包
│ ├── 完全背包
│ └── 多重背包
├── 树形DP
│ ├── 二叉树直径
│ └── 树的最大独立集
└── 状态压缩DP
├── 旅行商问题
└── 铺砖问题
5.2 学习路径建议
- 第一阶段（1-2周）：掌握入门级例题，理解DP基本思想
- 第二阶段（2-3周）：攻克进阶级例题，熟练状态定义和转移
- 第三阶段（3-4周）：挑战提高级例题，尝试综合应用
- 第四阶段（持续）：参加编程竞赛，解决实际工程问题
5.3 进一步学习资源
- 在线题库：
- LeetCode动态规划专题
- 洛谷动态规划专区
-
Codeforces DP标签题目
-
推荐书籍：
- 《算法导论》动态规划章节
- 《挑战程序设计竞赛》DP部分
-
《背包九讲》专题资料
-
实战项目：
- 编写自动求解简单DP问题的程序
- 实现可视化DP求解过程
- 参与算法竞赛周赛
致学生
动态规划是算法学习的难点，也是重点。记住： - 多练习：从简单题目开始，逐步增加难度 - 多总结：每做一题，总结状态定义和转移方程 - 多思考：不要只背模板，理解问题本质 - 多交流：和同学讨论，参加学习小组
坚持练习，你一定能掌握动态规划这门强大的算法工具！