【C++】动态规划从入门到醒目

一、动态规划基础概念详解

什么是动态规划
动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题解以避免重复计算的优化算法。它适用于具有以下两个关键性质的问题：
最优子结构：问题的最优解包罗子问题的最优解
重叠子问题：不同决策序列会重复求解雷同的子问题
下面用一些例子（由浅入深）了解动态规划
1.1 斐波那契数列递归实现解析

1. int fib(int n) {
2.     if(n <= 1) return n;          // 基准条件：F(0)=0, F(1)=1
3.     return fib(n-1) + fib(n-2);  // 递归分解为两个子问题
4. }

复制代码

代码解析：

• 递归终止条件：当n<=1时直接返回n值
  
• 递归关系：F(n) = F(n-1) + F(n-2)
  
• 问题分析：计算F(5)必要计算F(4)和F(3)，而计算F(4)又必要F(3)和F(2)，存在大量重复计算
  
• 时间复杂度：二叉树结构，O(2^n)，空间复杂度O(n)（调用栈深度）
  

1.2 记忆化递归实现解析

1. int memo[100] = {0};  // 全局记忆数组，默认初始化为0
3. int fib_memo(int n) {
4.     if(n <= 1) return n;
5.     if(memo[n] != 0)  // 检查是否已计算过
6.         return memo[n];
7.     return memo[n] = fib_memo(n-1) + fib_memo(n-2);  // 计算结果并存储
8. }

复制代码

代码解析：

• memo数组存储已计算结果，初始值为0表示未计算
  
• 每次递归调用前检查是否已有缓存结果
  
• 通过空间换时间，将重复计算转化为查表操纵
  
• 时间复杂度优化到O(n)，空间复杂度O(n)
  

1.3 迭代法实现解析

1. int fib_tab(int n) {
2.     if(n == 0) return 0;
3.     int dp[n+1];          // 创建DP表
4.     dp[0] = 0;            // 初始化基础条件
5.     dp[1] = 1;
6.     for(int i=2; i<=n; ++i)
7.         dp[i] = dp[i-1] + dp[i-2];  // 递推填充表格
8.     return dp[n];
9. }

复制代码

代码解析：

• dp数组索引对应斐波那契数列的位置
  
• 初始化前两个已知值
  
• 循环从2开始逐步构建后续结果
  
• 时间复杂度O(n)，空间复杂度O(n)（可优化为O(1)）
  

二、经典问题深度解析

2.1 最长公共子序列（LCS）完整解析

问题描述：给定两个字符串text1和text2，返回它们的最长公共子序列的长度

1. int lcs(string text1, string text2) {
2.     int m = text1.size(), n = text2.size();
3.     // 创建(m+1)x(n+1)的二维DP表，+1是为了处理空字符串的情况
4.     vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
6.     for(int i=1; i<=m; ++i) {
7.         for(int j=1; j<=n; ++j) {
8.             if(text1[i-1] == text2[j-1])  // 字符匹配（注意索引偏移）
9.                 dp[i][j] = dp[i-1][j-1] + 1;
10.             else  // 不匹配时取两个可能方向的最大值
11.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
12.         }
13.     }
14.     return dp[m][n];
15. }

复制代码

代码解析：

• 状态界说：dp[j]表示text1前i个字符与text2前j个字符的LCS长度
  
• 初始化：第一行和第一列初始为0，表示空字符串的情况
  
• 状态转移：
  
  
  
  • 当字符匹配时：LCS长度+1，继承左上方值+1
    
  • 当字符不匹配时：取上方或左方的最大值
    
  
  
• 遍历次序：双重循环按行填充表格
  
• 示例分析：
  text1 = “abcde”, text2 = “ace”
  DP表最终值为3（LCS为"ace"）
  

2.2 0-1背包问题完整解析

问题描述：给定物品重量数组wt和价值数组val，背包涵量W，求能装的最大价值

1. int knapsack(int W, vector<int>& wt, vector<int>& val) {
2.     int n = wt.size();
3.     vector<int> dp(W+1, 0);  // 一维DP数组优化空间
5.     for(int i=0; i<n; ++i) {            // 遍历每个物品
6.         for(int w=W; w>=wt[i]; --w) {   // 逆序更新防止覆盖
7.             dp[w] = max(dp[w],                    // 不选当前物品
8.                        dp[w - wt[i]] + val[i]);  // 选择当前物品
9.         }
10.     }
11.     return dp[W];
12. }

复制代码

代码解析：

• 状态界说：dp[w]表示容量为w时的最大价值
  
• 空间优化：利用一维数组替换二维数组
  
• 逆序遍历原因：包管每个物品只被考虑一次，避免重复利用
  
• 状态转移方程分析：
  
  
  
  • 不选物品i：价值保持dp[w]稳定
    
  • 选物品i：价值为dp[w-wt] + val
    
  
  
• 示例分析：
  W=4, wt=[2,3,4], val=[3,4,5]
  最终dp[4] = max(不选4: dp[4], 选4: dp[0]+5) = 5
  

2.3 编辑距离完整解析

问题描述：计算将word1转换成word2所需的最小操纵次数（插入、删除、替换）

1. int minDistance(string word1, string word2) {
2.     int m = word1.size(), n = word2.size();
3.     vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
5.     // 初始化边界条件
6.     for(int i=0; i<=m; ++i) dp[i][0] = i;  // 删除i次
7.     for(int j=0; j<=n; ++j) dp[0][j] = j;  // 插入j次
9.     for(int i=1; i<=m; ++i) {
10.         for(int j=1; j<=n; ++j) {
11.             if(word1[i-1] == word2[j-1]) {  // 字符相同无需操作
12.                 dp[i][j] = dp[i-1][j-1];
13.             } else {  // 选择三种操作中的最小代价
14.                 dp[i][j] = 1 + min({dp[i-1][j],   // 删除word1字符
15.                                   dp[i][j-1],   // 插入word2字符
16.                                   dp[i-1][j-1]});// 替换字符
17.             }
18.         }
19.     }
20.     return dp[m][n];
21. }

复制代码

代码解析：

• 状态界说：dp[j]表示转换前i个字符到前j个字符的最小操纵数
  
• 边界初始化：
  
  
  
  • 第一列表示将word1删成空串的操纵次数
    
  • 第一行表示将空串插入成word2的操纵次数
    
  
  
• 状态转移分析：
  
  
  
  • 字符匹配：直接继承左上方值
    
  • 字符不匹配：取三种操纵的最小值+1
    
  
  
• 操纵范例对应关系：
  
  
  
  • 删除：相当于处理word1的前i-1个字符
    
  • 插入：相当于处理word2的前j-1个字符
    
  • 替换：相当于处理i-1和j-1的情况后修改字符
    
  
  
• 示例分析：
  word1 = “horse”, word2 = “ros”
  最终编辑距离为3（替换h→r，删除 r，删除 e）
  

三、动态规划优化技巧详解

3.1 斐波那契数列空间优化

1. int fib_opt(int n) {
2.     if(n == 0) return 0;
3.     int prev = 0, curr = 1;  // 初始值F(0)=0, F(1)=1
4.     for(int i=2; i<=n; ++i) {
5.         int next = prev + curr;  // 计算下一个值
6.         prev = curr;  // 更新前一个值
7.         curr = next;  // 更新当前值
8.     }
9.     return curr;
10. }

复制代码

优化原理：

• 观察发现每个状态只依靠前两个状态
  
• 利用两个变量代替数组存储汗青值
  
• 空间复杂度从O(n)降到O(1)
  
• 滚动更新机制：
  
  
  
  • 每次迭代将prev更新为前一个curr
    
  • curr更新为新的计算结果
    
  
  

3.2 背包问题空间优化

1. // 二维原始版本
2. int dp[n+1][W+1];
4. // 优化为一维数组
5. vector<int> dp(W+1, 0);

复制代码

优化原理：

• 二维数组中每一行只依靠上一行的数据
  
• 逆序更新避免覆盖未利用的旧值
  
• 关键点：内层循环必须从W到wt逆序举行
  
• 示例说明：
  
  
  
  • 正序更新会导致物品被重复选取（完全背包问题）
    
  • 逆序更新包管每个物品只被考虑一次
    
  
  

四、动态规划解题方法论

4.1 状态界说技巧

• 确定问题变量维度：
  
  
  
  • 单序列问题（如LIS）：一维状态dp
    
  • 双序列问题（如LCS）：二维状态dp[j]
    
  • 带束缚问题（如背包）：二维状态dp[w]
    
  
  
• 常见状态界说模式：
  
  
  
  • “前i个元素…”：如dp表示前i个元素的最优解
    
  • “以第i个元素结尾…”：如最长递增子序列问题
    
  • “位置(i,j)…”：如矩阵路径问题
    
  
  

4.2 状态转移方程建立

• 分析子问题关系：
  
  
  
  • 怎样从较小规模的子问题推导当前问题
    
  • 举例：在编辑距离中，三种操纵对应三种子问题转移路径
    
  
  
• 方程建立步骤：
  (1) 列出全部大概的决策选项
  (2) 计算每个决策对应的子问题解
  (3) 选择最优决策并组合结果
  

4.3 初始化技巧

• 边界条件处理：
  
  
  
  • 空字符串/空聚集的处理
    
  • 初始值的物理意义（如背包涵量为0时价值为0）
    
  
  
• 特殊值初始化示例：
  
  1. // 矩阵路径问题初始化第一行和第一列
  2. for(int i=0; i<m; ++i) dp[i][0] = 1;
  3. for(int j=0; j<n; ++j) dp[0][j] = 1;

  复制代码

五、综合案例分析

5.1 最大子数组和

问题描述：求整数数组中和最大的连续子数组

1. int maxSubArray(vector<int>& nums) {
2.     int currMax = nums[0], globalMax = nums[0];
3.     for(int i=1; i<nums.size(); ++i) {
4.         // 决策：继续扩展子数组 or 重新开始
5.         currMax = max(nums[i], currMax + nums[i]);
6.         // 更新全局最大值
7.         globalMax = max(globalMax, currMax);
8.     }
9.     return globalMax;
10. }

复制代码

算法解析：

• 状态界说：currMax表示以当前元素结尾的最大子数组和
  
• 状态转移方程：
  currMax = max(nums, currMax + nums)
  
• 空间优化：仅需维护两个变量
  
• 示例分析：
  输入：[-2,1,-3,4,-1,2,1,-5,4]
  输出：6（子数组[4,-1,2,1]）
  

5.2 不同路径问题

问题描述：m x n网格从左上角到右下角的唯一路径数

1. int uniquePaths(int m, int n) {
2.     vector<vector<int>> dp(m, vector<int>(n, 1));
3.     for(int i=1; i<m; ++i) {
4.         for(int j=1; j<n; ++j) {
5.             dp[i][j] = dp[i-1][j] + dp[i][j-1];
6.         }
7.     }
8.     return dp[m-1][n-1];
9. }

复制代码

算法解析：

• 状态界说：dp[j]表示到达(i,j)的路径数
  
• 状态转移方程：dp[j] = 上方路径数 + 左方路径数
  
• 初始化技巧：第一行和第一列都只有1种路径
  
• 空间优化：可用一维数组替换，dp[j] += dp[j-1]
  

六、动态规划调试技巧

6.1 DP表可视化

• 打印DP表中间状态
  1. // 在LCS代码中插入调试输出
  2. for(auto& row : dp) {
  3.     for(int val : row) cout << val << " ";
  4.     cout << endl;
  5. }

  复制代码
• 观察表数据是否符合预期
  

6.2 边界测试用例

• 空输入测试：空字符串、空数组等
  
• 极值测试：n=0, W=0等特殊情况
  
• 示例测试：利用标题给出的示例验证
  

6.3 常见错误排查

• 数组越界：检查索引是否精确（特殊是从1开始的情况）
  
• 初始化错误：验证边界条件是否精确设置
  
• 循环次序错误：检查是否按精确依靠次序填充表格
  
• 状态转移方程错误：用简单用例手动验证
  

七、动态规划复杂度分析指南

7.1 时间复杂度计算

• 基本公式：状态数 × 每个状态的转移成本
  
  
  
  • LCS问题：O(mn)状态 × O(1)转移 = O(mn)
    
  • 背包问题：O(nW)状态 × O(1)转移 = O(nW)
    
  
  
• 多项式时间与伪多项式时间：
  
  
  
  • 背包问题的O(nW)称为伪多项式时间
    
  • 当W很大时（如指数级），算法服从会显著降落
    
  
  

7.2 空间复杂度优化

• 滚动数组技巧：
  
  
  
  • 二维→一维：当当前行只依靠前一行时
    
  • 示例：斐波那契数列、背包问题
    
  
  
• 状态压缩技巧：
  
  
  
  • 利用位运算表示状态聚集
    
  • 常见于观光商问题（TSP）等状压DP
    
  
  

八、动态规划进阶路线图

8.1 学习路径发起

• 基础阶段（1-2周）：
  
  
  
  • 斐波那契数列
    
  • 爬楼梯问题
    
  • 最大子数组和
    
  
  
• 提高阶段（2-4周）：
  
  
  
  • 背包问题系列
    
  • 字符串编辑问题
    
  • 矩阵路径问题
    
  
  
• 醒目阶段（1-2月）：
  
  
  
  • 树形DP（二叉树最大路径和）
    
  • 状态压缩DP（TSP问题）
    
  • 区间DP（矩阵链乘法）
    
  
  

8.2 推荐练习标题

标题范例LeetCode题号难度爬楼梯70简单最长递增子序列300中等零钱兑换322中等正则表达式匹配10困难交易股票最佳机遇121/123中等 九、动态规划代码模板库

9.1 一维DP模板

1. int dp[n];
2. dp[0] = initial_value;
4. for(int i=1; i<n; ++i) {
5.     dp[i] = compute(dp[...]);
6. }
8. return dp[n-1];

复制代码

9.2 二维DP模板

1. vector<vector<int>> dp(m, vector<int>(n, 0));
3. // 初始化边界
4. for(int i=0; i<m; ++i) dp[i][0] = ...;
5. for(int j=0; j<n; ++j) dp[0][j] = ...;
7. // 填充表格
8. for(int i=1; i<m; ++i) {
9.     for(int j=1; j<n; ++j) {
10.         dp[i][j] = compute(dp[i-1][j], dp[i][j-1], ...);
11.     }
12. }

复制代码

十、动态规划常见问题FAQ

Q：怎样判断一个问题是否可以用DP解决？
A：检查问题是否具有：

• 最优子结构性质
  
• 重叠子问题性质
  
• 无后效性（当前决策不影响之前状态）
  

Q：DP和分治法的区别是什么？
A：分治法将问题分解为独立的子问题，而DP处理的是重叠的子问题
Q：怎样处理环形结构问题？
A：常用技巧：

• 破环成链（复制数组）
  
• 分类讨论（考虑包罗首元素和不包罗的情况）
  

Q：怎样选择记忆化递归还是迭代法？
A：

• 记忆化递归更直观，得当树形结构问题
  
• 迭代法服从更高，得当必要空间优化的情况
  
• 动态规划导图
  
  
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。