【C++】动态规划从入门到醒目
一、动态规划基础概念详解什么是动态规划
动态规划（Dynamic Programming，DP）是一种通过将复杂问题分解为重叠子问题，并存储子问题解以避免重复计算的优化算法。它适用于具有以下两个关键性质的问题：
最优子结构：问题的最优解包罗子问题的最优解
重叠子问题：不同决策序列会重复求解雷同的子问题
下面用一些例子（由浅入深）了解动态规划
1.1 斐波那契数列递归实现解析
int fib(int n) {
if(n <= 1) return n; // 基准条件：F(0)=0, F(1)=1
return fib(n-1) + fib(n-2);// 递归分解为两个子问题
}
代码解析：
[*]递归终止条件：当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 记忆化递归实现解析
int memo = {0};// 全局记忆数组，默认初始化为0
int fib_memo(int n) {
if(n <= 1) return n;
if(memo != 0)// 检查是否已计算过
return memo;
return memo = fib_memo(n-1) + fib_memo(n-2);// 计算结果并存储
}
代码解析：
[*]memo数组存储已计算结果，初始值为0表示未计算
[*]每次递归调用前检查是否已有缓存结果
[*]通过空间换时间，将重复计算转化为查表操纵
[*]时间复杂度优化到O(n)，空间复杂度O(n)
1.3 迭代法实现解析
int fib_tab(int n) {
if(n == 0) return 0;
int dp; // 创建DP表
dp = 0; // 初始化基础条件
dp = 1;
for(int i=2; i<=n; ++i)
dp = dp + dp;// 递推填充表格
return dp;
}
代码解析：
[*]dp数组索引对应斐波那契数列的位置
[*]初始化前两个已知值
[*]循环从2开始逐步构建后续结果
[*]时间复杂度O(n)，空间复杂度O(n)（可优化为O(1)）
二、经典问题深度解析
2.1 最长公共子序列（LCS）完整解析
问题描述：给定两个字符串text1和text2，返回它们的最长公共子序列的长度
int lcs(string text1, string text2) {
int m = text1.size(), n = text2.size();
// 创建(m+1)x(n+1)的二维DP表，+1是为了处理空字符串的情况
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 == text2)// 字符匹配（注意索引偏移）
dp = dp + 1;
else// 不匹配时取两个可能方向的最大值
dp = max(dp, dp);
}
}
return dp;
}
代码解析：
[*]状态界说：dp表示text1前i个字符与text2前j个字符的LCS长度
[*]初始化：第一行和第一列初始为0，表示空字符串的情况
[*]状态转移：
[*]当字符匹配时：LCS长度+1，继承左上方值+1
[*]当字符不匹配时：取上方或左方的最大值
[*]遍历次序：双重循环按行填充表格
[*]示例分析：
text1 = “abcde”, text2 = “ace”
DP表最终值为3（LCS为"ace"）
2.2 0-1背包问题完整解析
问题描述：给定物品重量数组wt和价值数组val，背包涵量W，求能装的最大价值
int knapsack(int W, vector<int>& wt, vector<int>& val) {
int n = wt.size();
vector<int> dp(W+1, 0);// 一维DP数组优化空间
for(int i=0; i<n; ++i) { // 遍历每个物品
for(int w=W; w>=wt; --w) { // 逆序更新防止覆盖
dp = max(dp, // 不选当前物品
dp] + val);// 选择当前物品
}
}
return dp;
}
代码解析：
[*]状态界说：dp表示容量为w时的最大价值
[*]空间优化：利用一维数组替换二维数组
[*]逆序遍历原因：包管每个物品只被考虑一次，避免重复利用
[*]状态转移方程分析：
[*]不选物品i：价值保持dp稳定
[*]选物品i：价值为dp] + val
[*]示例分析：
W=4, wt=, val=
最终dp = max(不选4: dp, 选4: dp+5) = 5
2.3 编辑距离完整解析
问题描述：计算将word1转换成word2所需的最小操纵次数（插入、删除、替换）
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
// 初始化边界条件
for(int i=0; i<=m; ++i) dp = i;// 删除i次
for(int j=0; j<=n; ++j) dp = j;// 插入j次
for(int i=1; i<=m; ++i) {
for(int j=1; j<=n; ++j) {
if(word1 == word2) {// 字符相同无需操作
dp = dp;
} else {// 选择三种操作中的最小代价
dp = 1 + min({dp, // 删除word1字符
dp, // 插入word2字符
dp});// 替换字符
}
}
}
return dp;
}
代码解析：
[*]状态界说：dp表示转换前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 斐波那契数列空间优化
int fib_opt(int n) {
if(n == 0) return 0;
int prev = 0, curr = 1;// 初始值F(0)=0, F(1)=1
for(int i=2; i<=n; ++i) {
int next = prev + curr;// 计算下一个值
prev = curr;// 更新前一个值
curr = next;// 更新当前值
}
return curr;
}
优化原理：
[*]观察发现每个状态只依靠前两个状态
[*]利用两个变量代替数组存储汗青值
[*]空间复杂度从O(n)降到O(1)
[*]滚动更新机制：
[*]每次迭代将prev更新为前一个curr
[*]curr更新为新的计算结果
3.2 背包问题空间优化
// 二维原始版本
int dp;
// 优化为一维数组
vector<int> dp(W+1, 0);
优化原理：
[*]二维数组中每一行只依靠上一行的数据
[*]逆序更新避免覆盖未利用的旧值
[*]关键点：内层循环必须从W到wt逆序举行
[*]示例说明：
[*]正序更新会导致物品被重复选取（完全背包问题）
[*]逆序更新包管每个物品只被考虑一次
四、动态规划解题方法论
4.1 状态界说技巧
[*] 确定问题变量维度：
[*]单序列问题（如LIS）：一维状态dp
[*]双序列问题（如LCS）：二维状态dp
[*]带束缚问题（如背包）：二维状态dp
[*] 常见状态界说模式：
[*]“前i个元素…”：如dp表示前i个元素的最优解
[*]“以第i个元素结尾…”：如最长递增子序列问题
[*]“位置(i,j)…”：如矩阵路径问题
4.2 状态转移方程建立
[*] 分析子问题关系：
[*]怎样从较小规模的子问题推导当前问题
[*]举例：在编辑距离中，三种操纵对应三种子问题转移路径
[*] 方程建立步骤：
(1) 列出全部大概的决策选项
(2) 计算每个决策对应的子问题解
(3) 选择最优决策并组合结果
4.3 初始化技巧
[*] 边界条件处理：
[*]空字符串/空聚集的处理
[*]初始值的物理意义（如背包涵量为0时价值为0）
[*] 特殊值初始化示例：
// 矩阵路径问题初始化第一行和第一列
for(int i=0; i<m; ++i) dp = 1;
for(int j=0; j<n; ++j) dp = 1;
五、综合案例分析
5.1 最大子数组和
问题描述：求整数数组中和最大的连续子数组
int maxSubArray(vector<int>& nums) {
int currMax = nums, globalMax = nums;
for(int i=1; i<nums.size(); ++i) {
// 决策：继续扩展子数组 or 重新开始
currMax = max(nums, currMax + nums);
// 更新全局最大值
globalMax = max(globalMax, currMax);
}
return globalMax;
}
算法解析：
[*]状态界说：currMax表示以当前元素结尾的最大子数组和
[*]状态转移方程：
currMax = max(nums, currMax + nums)
[*]空间优化：仅需维护两个变量
[*]示例分析：
输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6（子数组）
5.2 不同路径问题
问题描述：m x n网格从左上角到右下角的唯一路径数
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 1));
for(int i=1; i<m; ++i) {
for(int j=1; j<n; ++j) {
dp = dp + dp;
}
}
return dp;
}
算法解析：
[*]状态界说：dp表示到达(i,j)的路径数
[*]状态转移方程：dp = 上方路径数 + 左方路径数
[*]初始化技巧：第一行和第一列都只有1种路径
[*]空间优化：可用一维数组替换，dp += dp
六、动态规划调试技巧
6.1 DP表可视化
[*]打印DP表中间状态// 在LCS代码中插入调试输出
for(auto& row : dp) {
for(int val : row) cout << val << " ";
cout << endl;
}
[*]观察表数据是否符合预期
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模板
int dp;
dp = initial_value;
for(int i=1; i<n; ++i) {
dp = compute(dp[...]);
}
return dp;
9.2 二维DP模板
vector<vector<int>> dp(m, vector<int>(n, 0));
// 初始化边界
for(int i=0; i<m; ++i) dp = ...;
for(int j=0; j<n; ++j) dp = ...;
// 填充表格
for(int i=1; i<m; ++i) {
for(int j=1; j<n; ++j) {
dp = compute(dp, dp, ...);
}
}
十、动态规划常见问题FAQ
Q：怎样判断一个问题是否可以用DP解决？
A：检查问题是否具有：
[*]最优子结构性质
[*]重叠子问题性质
[*]无后效性（当前决策不影响之前状态）
Q：DP和分治法的区别是什么？
A：分治法将问题分解为独立的子问题，而DP处理的是重叠的子问题
Q：怎样处理环形结构问题？
A：常用技巧：
[*]破环成链（复制数组）
[*]分类讨论（考虑包罗首元素和不包罗的情况）
Q：怎样选择记忆化递归还是迭代法？
A：
[*]记忆化递归更直观，得当树形结构问题
[*]迭代法服从更高，得当必要空间优化的情况
[*]动态规划导图
https://i-blog.csdnimg.cn/direct/dbab68c96c3c4eecb31fa13c5ca87ff8.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]