动态规划算法Dynamic Programming一、算法核心原理1.1 基本思想动态规划是一种将复杂问题分解为简单子问题的算法设计范式。与分治法不同动态规划解决的问题通常具有重叠子问题和最优子结构的特性。1.2 核心要素1.最优子结构问题的最优解包含子问题的最优解2.重叠子问题递归求解时会重复计算相同的子问题。3.状态转移如何从较小的子问题推导出较大问题的解。二、算法步骤2.1 四步法1.定义状态2.确定状态转移方程3.设置初始条件4.确定计算顺序5.返回最终结果三、实现方式对比3.1自顶向下记忆化搜索优点思路直观类似递归缺点递归开销可能栈溢出3.2 自底向上递推优点高效无递归开销缺点需要明确计算顺序四、经典问题实现4.1 斐波那契数列问题描述计算第n个斐波那契数#includeiostream#includevectorusingnamespacestd;//方法1 朴素递归时间复杂度高不推荐intfib_recursive(intn){if(n1)returnn;returnfib_recursive(n-1)*fib_recursive(n-2);}//方法2自顶向下记忆化搜索intfib_memo(intn,vectorintmemo){if(n1)returnn;if(memo[n]!-1)returnmemo[n];memo[n]fib_meo(n-1,memo)fib_memo(n-2,memo);returnmemo[n];}intfib_top_down(intn){vectorintmemo(n1,-1);returnfib_memo(n,memo);}//方法3自底向上递推intfib_bottom_up(intn){if(n1)returnn;vectorintdp(n1,0);dp[0]0;dp[1]1;for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}//方法4空间优化版本intfib_optimized(intn){if(n1)returnn;intprev20;//dp[i-2];intprev11;//dp[i-1];intcurrent;//dp[i];for(inti2;in;i){currentprev1prev2;prev2prev1;prev1current;}returncurrent;}复杂度分析朴素递归时间复杂度O(2^n), 空间复杂度On记忆优化搜索时间复杂度O(n),空间复杂度O(n)自底向上时间复杂度O(n),空间复杂度O(n)优化版本时间复杂度O(n),空间复杂度O(1)4.2 0-1背包问题问题描述从n个物品中选择每个物品有重量和价值背包容量有限求最大价值。#includevector#includeiostream#includealgorithmusingnamespacestd;//方法一基础二维DPintknapsack_2d(intW,vectorintwt,vectorintval,intn){//d[i][w] 表示考虑前i个物品容量为w时的最大价值vectorvectorintdp(n1,vectorint(W1,0));for(inti1;in;i){for(intwi;wW;w){//不选第i个物品dp[i][w]dp[i-1][w];//如果能放得下考虑选第i个物品if(wwt[i-1]){dp[i][w]max(dp[i][w],dp[i-1][w-wt[i-1]]val[i-1]);}}}}//方法二一维DP优化滚动数组intknapsack_1d(intW,vectorintwt,vectorintval,intn){vectorintdp(W1,0);for(inti0;in;i){//必须倒序遍历保证每个物品只被计算一次for(intwW;wwt[i];w--){dp[w]max(dp[w],dp[w-wt[i]]val[i]);}}returndp[W];}//方法三:带路径记录voidknapsack_with_path(intW,vectorintwt,vectorintval,intn){//d[i][w] 表示考虑前i个物品容量为w时的最大价值vectorvectorintdp(n1,vectorint(W1,0));// 填充DP表for(inti1;in;i){for(intw1;wW;w){if(wwt[i-1]){dp[i][w]max(dp[i-1][w],dp[i-1][w-wt[i-1]]val[i-1]);}else{dp[i][w]dp[i-1][w];}}}// 回溯找选择的物品cout最大价值: dp[n][W]endl;cout选择的物品: ;intwW;for(intin;i0w0;i--){if(dp[i][w]!dp[i-1][w]){couti ;// 选择第i个物品w-wt[i-1];}}coutendl;}复杂度分析时间复杂度O(nW),其中n为物品数W为背包容量空间复杂度二维O(n*w), 一维O(W)4.3最长公共子序列问题描述求两个序列的最长公共子序列长度#includeiostream#includevector#includestring#includealgorithmusingnamespacestd;intlongestCommSubSequence(string text1,string text2){intmtext1.length();intntext2.length();//dp[i][j] 表示text1[0....i-1]和tex2[0...j-1]的LCS长度vectorvectorintdp(m1,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;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]);}}}returndp[m][n];}//空间优化版本intlongestCommSubSequence_opt(string text1,string text2){intmtext1.length();intntext2.length();if(mn){swap(text1,text2);swap(m,n);}vectorvectorintdp(2,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;j){if(text1[i-1]text2[j-1]){dp[i%2][j]dp[(i-1)%2][j-1]1;}else{dp[i%2][j]max(dp[(i-1)%2][j],dp[i%2][j-1]);}}}returndp[m%2][n];}复杂度分析时间复杂度Om*n空间复杂度优化前O(m*n) ,优化后O(min(m,n))五、 复杂度总结5.1 时间复杂度动态规划的时间复杂度通常由以下因素决定状态数量通常是多维度的乘积状态转移复杂度每个状态计算需要的操作数计算顺序确保子问题已经求解一般公式时间复杂度状态数量*单个状态转移复杂度5.2空间复杂度优化技巧1.滚动数组// 二维降一维vectorintdp(W1,0);for(inti0;in;i){for(intwW;wwt[i];w--){// 注意遍历顺序dp[w]max(dp[w],dp[w-wt[i]]val[i]);}}2.状态压缩适用于状态较少的情况int dp[1n][n]; // 用二进制位表示城市访问状态3.降维技巧// 如果当前状态只依赖前一行/前一列// 可以使用两个一维数组交替vectorintprev(W1,0),curr(W1,0);for(inti0;in;i){swap(prev,curr);for(intw0;wW;w){// 计算curr[w]}}六、模版代码classDPSolution{public:// 通用框架intsolveDP(intn,intm){// 1. 定义状态vectorvectorintdp(n1,vectorint(m1,0));// 2. 初始化for(inti0;in;i)dp[i][0]1;for(intj0;jm;j)dp[0][j]1;// 3. 状态转移for(inti1;in;i){for(intj1;jm;j){// 状态转移方程dp[i][j]dp[i-1][j]dp[i][j-1];}}// 4. 返回结果returndp[n][m];}};