动态规划讲解

一. 什么是动态规划动态规划Dynamic Programming简称 DP是一种求最优解的方法通过将复杂问题分解为相对简单的问题并存储子问题的解以便在下次需要同一个子问题的解时直接查表根据子问题的解求出原问题。核心是“最优子结构”和“重叠子问题”两个特性。它和递归的区别在于递归是自顶向下重复计算子问题先递把大问题分解成小问题直到触达递归终止条而动态规划是自底向上先解决小问题再用小问题的解推导大问题的解通过 “记忆化存储” 大幅降低时间复杂度。例如斐波那契数列定义如下Fib(n)1; n0;Fib(n)1; n1;Fib(n)Fib(n-1)Fib(n-2); n1;如果给你一个n求Fib(n),使用递归实现的算法如下#include iostream using namespace std; long long Fib(int n) { if (n 0 || n 1) { return 1; // 对应定义中的初始项 } return Fib(n-1) Fib(n-2); } int main() { int n; cout 输入n; cin n; cout Fib( n ) Fib(n) endl; return 0; }分析如求Fib(4)重复的子问题如Fib(2)被计算两次不会共享中间结果每次调用都会重新创建栈帧、重新计算这也是基础递归性能差的根源动态规划求解#define _CRT_SECURE_NO_WARNINGS #define MAXN 100 #include stdio.h int fib3(int n) { int dp[MAXN];//明确了数组dp的大小为 100此时dp数组可存储索引 0~99 的斐波那契数 dp[0] dp[1] 1; for (int i 2; i n; i) { dp[i]dp[i-2]dp[i-1]; } return dp[n]; } int main() { int a 0; scanf(%d, a); int b fib3(a); printf(%d, b); }讲解1. 明确的「状态定义」DP 数组的含义代码中定义了数组dp[MAXN]其中dp[i]是明确的状态定义表示斐波那契数列的第i项的值。通过这个状态定义我们将 “求斐波那契第n项” 这个原问题转化为了 “求dp[n]” 这个子问题的集合先求dp[2]、dp[3]... 最终求dp[n]。2. 清晰的「状态转移方程」子问题的递推关系状态转移方程是动态规划的核心描述了 “如何从已解决的子问题推导出当前子问题的解”代码中的dp[i] dp[i-2] dp[i-1]就是标准的状态转移方程。含义第i项斐波那契数dp[i]可以由它的前两项子问题dp[i-1]和dp[i-2]的解相加得到这正是斐波那契数列的定义也是动态规划 “递推” 思想的体现。3. 确定的「边界条件」子问题的终止条件动态规划的递推需要有 “起点”即最基础的子问题无需再分解的问题这就是边界条件代码中的dp[0] dp[1] 1是明确的边界条件。含义第 0 项和第 1 项斐波那契数是已知的均为 1这两个子问题无需再通过其他子问题推导是整个递推过程的起点后续所有dp[i]i≥2都基于这两个边界值展开计算。4. 「重叠子问题」的优化通过 DP 数组缓存避免重复计算这是动态规划与普通递归的核心区别也是动态规划的效率优势所在先回顾普通递归的问题计算dp[4]时需要计算dp[3]和dp[2]计算dp[3]时又需要重复计算dp[2]和dp[1]dp[2]就是重叠子问题会被多次计算。这段代码的优化方式通过dp数组相当于 “缓存容器”将每个子问题dp[0]到dp[n]的解只计算一次并存储在数组中。当后续计算需要用到前面的子问题解时直接从数组中读取无需重新计算彻底消除了重叠子问题的重复计算将时间复杂度从递归的O(2^n)降至O(n)。5. 「自底向上」的求解顺序从基础子问题到原问题求解顺序先计算最基础的边界值dp[0]、dp[1]底层子问题再依次计算dp[2]、dp[3]、...、dp[n]逐层向上推导最终得到原问题dp[n]的解。这种顺序无需递归调用直接通过循环实现既避免了递归的栈开销也保证了每个子问题按依赖顺序被求解。详细过程第 1 次循环i2计算dp[2]初始化循环变量i2判断2 4条件成立进入循环体执行dp[i] dp[i-2] dp[i-1]即dp[2] dp[0] dp[1]代入已知值dp[2] 1 1 2将2存入数组索引 2 的位置此时dp[2]2循环变量i自增 1变为3。第 2 次循环i3计算dp[3]判断3 4条件成立进入循环体执行dp[3] dp[1] dp[2]代入已知值dp[3] 1 2 3将3存入数组索引 3 的位置此时dp[3]3循环变量i自增 1变为4。第 3 次循环i4计算dp[4]判断4 4条件成立进入循环体执行dp[4] dp[2] dp[3]代入已知值dp[4] 2 3 5将5存入数组索引 4 的位置此时dp[4]5循环结束判断5 4条件不成立跳出for循环此时dp数组的前 5 个元素已确定dp[0]1、dp[1]1、dp[2]2、dp[3]3、dp[4]5其余元素仍为垃圾值。优化#define _CRT_SECURE_NO_WARNINGS #define MAXN 100 #include stdio.h //int fib3(int n) //{ // int dp[MAXN];//明确了数组dp的大小为 100此时dp数组可存储索引 0~99 的斐波那契数 // dp[0] dp[1] 1; // for (int i 2; i n; i) // { // dp[i]dp[i-2]dp[i-1]; // } // return dp[n]; //} int fib4(int n) { int dp [3]; dp[0] dp[1] 1; for (int i 2; i n; i) { dp[i%3] dp[(i - 2) % 3] dp[(i - 1) % 3]; } return dp[n%3]; } int main() { int a 0; scanf(%d, a); int b fib4(a); printf(%d, b); }分析一、核心原理斐波那契数列的递推仅依赖 “前两项”斐波那契数列的状态转移方程是dp[i] dp[i-2] dp[i-1]这意味着计算第i项时只需要用到第i-1项和第i-2项的值不需要保留更早之前的所有项原始fib3用长度 100 的数组存储所有项是 “冗余” 的我们只需要有限的存储空间来保存 “前两项” 即可这里用长度 3 的数组是这种思想的延伸本质和用 2 个变量迭代是一致的只是通过数组 取模实现了更规整的存储切换。二、取模运算i%3的核心作用循环复用数组空间数组dp的长度为 3索引为 0、1、2i%3的作用是将递增的i2,3,4,5...映射到固定的数组索引0,1,2上从而循环覆盖数组中 “无用” 的旧数据实现有限空间的复用取模运算规律对于i≥2i%3的结果会按2→0→1→2→0→1...的顺序循环意思是与3的余数只能为0,1,2 不会大于3。关键逻辑dp[i%3]存储当前第i项的值dp[(i-1)%3]和dp[(i-2)%3]恰好能精准定位到 “前两项” 的值因为取模映射保持了 “前两项” 的依赖关系本质用长度 3 的数组模拟了 “循环缓冲区”旧的、不再需要的数据会被新计算的值覆盖无需额外的内存空间。例子fib3(4):以n4求解第 4 项为例逐步骤验证执行过程我们跟着代码逻辑一步步走清晰看到数组空间的复用和计算过程步骤 1初始化fib4函数定义并初始化数组dpint dp[3]; // 定义长度为3的数组初始值为垃圾值 dp[0] dp[1] 1; // 初始化边界条件dp[0]1dp[1]1dp[2]仍为垃圾值此时数组状态dp[0]1、dp[1]1、dp[2]?无用垃圾值步骤 2执行for循环i从 2 到 4n4循环条件for (int i 2; i 4; i)共执行 3 次循环每次通过i%3映射数组索引第 1 次循环i2计算第 2 项计算索引映射i%3 2%3 2当前项存储索引(i-2)%3 0%3 0前第 2 项索引(i-1)%3 1%3 1前第 1 项索引执行赋值dp[2] dp[0] dp[1] 1 1 2此时数组状态dp[0]1、dp[1]1、dp[2]2第 2 项值为 2第 2 次循环i3计算第 3 项计算索引映射i%3 3%3 0当前项存储索引覆盖原 dp [0](i-2)%3 1%3 1前第 2 项索引对应原 dp [1]1(i-1)%3 2%3 2前第 1 项索引对应 dp [2]2执行赋值dp[0] dp[1] dp[2] 1 2 3此时数组状态dp[0]3第 3 项值覆盖了原 1、dp[1]1、dp[2]2第 3 次循环i4计算第 4 项计算索引映射i%3 4%3 1当前项存储索引覆盖原 dp [1](i-2)%3 2%3 2前第 2 项索引对应 dp [2]2(i-1)%3 3%3 0前第 1 项索引对应 dp [0]3执行赋值dp[1] dp[2] dp[0] 2 3 5此时数组状态dp[0]3、dp[1]5第 4 项值覆盖了原 1、dp[2]2步骤 3返回结果执行return dp[n%3]n44%31返回dp[1]5与斐波那契数列第 4 项按代码边界定义的结果一致。二.动态规划求解问题的类型性质和步骤1.求解问题的类型求目标函数指定的最值最大值或者最小值判断某个条件是否可行统计满足某个条件的方案数2.动态规划求解问题的性质并非所有问题都适合用动态规划求解只有满足以下两个核心性质的问题才能通过动态规划高效求解这也是动态规划算法设计的前提条件1. 最优子结构性质问题的最优解包含其子问题的最优解。也就是说若将原问题分解为若干个子问题当原问题达到最优时其包含的每个子问题也必然是最优的。这一性质是动态规划能够“自底向上推导最优解的基础——我们可以通过求解子问题的最优解逐步组合得到原问题的最优解。例如在最短路径问题中从起点A到终点C的最短路径若经过中间节点B则该路径中从A到B的子路径必然是A到B的最短路径若存在更短的A到B子路径替换后可得到更短的A到C路径与原路径是最优解矛盾这就验证了最优子结构性质。2. 子问题重叠性质在求解原问题的过程中会反复遇到相同的子问题而非每次遇到的子问题都是全新的。这一性质是动态规划能够通过“状态记忆”如备忘录、DP数组提升效率的关键——若子问题不重叠动态规划与普通的分治法效率差异不大但当子问题大量重叠时动态规划可通过记录已求解子问题的结果避免重复计算将时间复杂度从穷举的指数级降低到多项式级。例如在计算斐波那契数列时直接递归会反复计算f(5)、f(4)等子问题而动态规划通过DP数组记录f(1)到f(n)的结果每个子问题仅计算一次效率大幅提升。但重叠子问题不是动态规划算法的必备条件3. 无后效性性质也称“状态无后效性”指当前状态的决策仅依赖于当前状态本身与当前状态之前的决策路径无关同时当前决策仅影响未来的状态对过去的状态无回溯影响。这一性质确保了动态规划的状态定义是有效的——我们可以通过“状态”封装过去的决策信息无需关注决策路径的细节只需基于当前状态推导后续状态。例如在背包问题中当前的状态定义为“已选择的物品总重量”和“已获得的总价值”无论之前选择的是哪些物品路径不同只要总重量和总价值相同后续的决策是否选择下一个物品是完全一致的这就是无后效性的体现。3动态规划求解问题的步骤动态规划的求解过程遵循固定的逻辑框架核心是“状态定义→状态转移→边界初始化→结果推导”具体步骤可细化为以下五步1. 问题拆解识别子问题首先分析原问题的结构将其拆解为若干个规模更小、性质相同的子问题。这一步的关键是找到问题的“多阶段决策”特征明确子问题与原问题的关联——原问题的解可由子问题的解组合得到。例如求解“从A到C的最短路径”可拆解为“从A到B的最短路径”和“从B到C的最短路径”两个子问题求解“n个物品的0-1背包问题”可拆解为“n-1个物品的背包问题不选第n个物品”和“n-1个物品的背包问题选第n个物品背包容量减去第n个物品的重量”两个子问题。2. 状态定义封装子问题的核心信息状态是动态规划的核心用于描述子问题的关键信息其定义的合理性直接决定了动态规划算法的可行性与效率。状态的定义需满足“无后效性”且能完整覆盖子问题的核心约束与目标。通常用一个或多个参数来描述状态并用DP数组或备忘录记录状态对应的最优解。例如0-1背包问题状态定义为dp[i][j]表示“前i个物品中选择部分物品放入容量为j的背包可获得的最大价值”其中i物品数量和j背包容量是状态参数dp[i][j]是状态对应的最优解最长公共子序列问题状态定义为dp[i][j]表示“字符串s1的前i个字符与字符串s2的前j个字符的最长公共子序列长度”i和j是状态参数dp[i][j]是最优解。3. 状态转移方程建立子问题与原问题的关联状态转移方程是动态规划的“核心逻辑”用于描述当前状态的最优解如何由其他状态子问题的最优解推导得到。其本质是梳理“决策选择”与“状态变化”的关系——对于当前状态枚举所有可能的决策选择能使当前状态最优的决策进而推导对应的状态转移。例如0-1背包问题的状态转移方程对于第i个物品有两种决策选或不选。若不选dp[i][j] dp[i-1][j]继承前i-1个物品在容量j下的最优价值若选需满足j ≥ 物品i的重量w[i]dp[i][j] dp[i-1][j - w[i]] v[i]前i-1个物品在容量j - w[i]下的最优价值加上物品i的价值。因此状态转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])j ≥ w[i]时否则dp[i][j] dp[i-1][j]最长公共子序列问题的状态转移方程若s1[i] s2[j]当前字符相同则dp[i][j] dp[i-1][j-1] 1最长公共子序列长度加1若s1[i] ≠ s2[j]则dp[i][j] max(dp[i-1][j], dp[i][j-1])取“s1前i-1个与s2前j个”或“s1前i个与s2前j-1个”的最长长度。4. 边界条件初始化确定最小子问题的解边界条件是状态转移的“起点”对应规模最小的子问题无法再拆解的子问题其最优解是已知的无需通过状态转移推导。边界条件的初始化直接影响后续所有状态的计算准确性需结合问题场景明确。例如0-1背包问题的边界当i0无物品可选时无论背包容量j多大最大价值均为0即dp[0][j] 0当j0背包容量为0无法装任何物品时无论有多少物品最大价值均为0即dp[i][0] 0最长公共子序列问题的边界当i0s1为空字符串或j0s2为空字符串时最长公共子序列长度为0即dp[0][j] 0、dp[i][0] 0。5. 计算最优解自底向上或自顶向下推导根据状态转移方程和边界条件通过“自底向上”或“自顶向下”的方式计算所有状态的最优解最终得到原问题的最优解。自底向上迭代法从边界条件出发按照子问题规模从小到大的顺序逐步计算所有中间状态的最优解最终推导到原问题对应的状态。这种方式通常使用DP数组实现效率较高无递归栈开销。例如0-1背包问题中先计算i1第一个物品在不同j下的dp[1][j]再计算i2前两个物品的dp[2][j]直至计算到in所有物品、jV背包总容量的dp[n][V]即为原问题的最优解自顶向下递归备忘录法从原问题出发通过递归拆解为子问题若子问题已求解则直接调用备忘录中的结果未求解则计算后存入备忘录。这种方式更符合问题的拆解逻辑适用于子问题规模不均匀的场景但需注意递归栈溢出问题。例如计算斐波那契数列的f(n)时递归调用f(n-1)和f(n-2)通过备忘录记录已计算的f(k)避免重复计算。此外部分问题在计算完成后可能需要根据DP数组回溯推导具体的最优方案如背包问题中选择了哪些物品、最长公共子序列的具体字符这一步需结合状态转移方程的逻辑反向推导决策路径。二.实战1.最长公共子序列给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。示例 1输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace 它的长度为 3 。示例 2输入text1 abc, text2 abc输出3解释最长公共子序列是 abc 它的长度为 3 。示例 3输入text1 abc, text2 def输出0解释两个字符串没有公共子序列返回 0 。思路