一、什么是动态规划动态规划Dynamic Programming, DP是一种解决多阶段决策问题的算法思想。它通过把原问题分解为重叠的子问题并保存子问题的解避免大量重复计算从而将指数级的时间复杂度降为多项式级别。适用场景问题可以分解成相互依赖的子问题子问题会被多次重复计算子问题的最优解能构成原问题的最优解最优子结构二、核心概念状态定义用一个或多个变量描述当前所处的情形通常用数组下标表示。例如 dp[i] 表示“前 i 个物品的最大价值”或 dp[i][j] 表示“字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度”。状态转移方程描述状态之间如何推导的数学表达式是 DP 的核心。比如 0-1 背包dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])初始条件 / 边界最小的子问题的解通常是 dp[0]、dp[0][0] 等。计算顺序确定按什么顺序填充 DP 表格保证计算当前状态时依赖的状态已经算过。三、动态规划的一般解题步骤分析问题是否有重叠子问题和最优子结构定义状态明确 dp[i] 或 dp[i][j] 代表什么推导状态转移方程初始化边界确定遍历顺序用代码实现可能的空间优化用滚动数组代替二维数组四、经典例题C 代码斐波那契数列问题求第 n 项斐波那契数 F(0)0, F(1)1, F(n)F(n-1)F(n-2)#includeiostream#includevectorusingnamespacestd;longlongfib(intn){if(n1)returnn;vectorlonglongdp(n1);dp[0]0;dp[1]1;for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}intmain(){coutfib(50)endl;return0;}背包问题问题有 n 个物品每个物品重量 w[i]价值 v[i]背包容量为 W每种物品只能选 0 或 1 个求最大总价值。状态定义dp[i][j] —— 前 i 个物品放入容量为 j 的背包的最大价值。intknapsack(intW,vectorintweight,vectorintvalue){intnweight.size();vectorvectorintdp(n1,vectorint(W1,0));for(inti1;in;i){intwweight[i-1],vvalue[i-1];for(intj1;jW;j){if(jw)dp[i][j]dp[i-1][j];elsedp[i][j]max(dp[i-1][j],dp[i-1][j-w]v);}}returndp[n][W];}五、总结动态规划是一门需要大量练习才能熟练掌握的技艺。本质是 “以空间换时间”通过数组表格记录子问题的解避免重复运算。学习路线建议先用递归写暴力解画出递归树发现重叠子问题改为记忆化搜索自顶向下推导 DP 表自底向上
