动态规划（DP）算法实战指南：从状态定义到状态转移的完整解题框架

教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载动态规划Dynamic ProgrammingDP是算法学习中最重要也最考验思维的算法设计范式之一。本文以 8 Algorithms Analysis/动态规划.md 为核心骨架结合本仓库中 递归.md、分治算法.md、回溯法.md 等算法分析文档以及 fibonacci.c 等源码实现系统讲解 DP 的核心思想、适用场景、与其他算法的边界并以「最大子数组和」「凑零钱」「股票买卖」「接雨水」四大经典问题为主线给出可直接复用的解题模板与代码。读完本文你将掌握「状态定义 → 状态转移方程 → 状态压缩」的标准 DP 解题流程并能独立分析面试中高频出现的动规题型。什么是动态规划分治 解决冗余动态规划Dynamic Programming简称 DP是通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。与分治不同复杂问题不能分解成几个独立的子问题而是分解成一系列相互关联的子问题。DP 通常基于一个递推公式及一个或多个初始状态当前子问题的解由上一次子问题的解推出。它的核心可以用两句话概括动态规划算法的关键在于解决冗余是以空间换时间的技术——需要存储过程中各种状态动态规划算法也可以说是记住求过的解来节省时间。以 Fibonacci 数列为例先从最小、最简单的 f(1)、f(2) 开始自底向上一直递推到 f(20)这就是动态规划的思路。整个过程可以抽象为一条状态链【初始状态】→【决策1】→【决策2】→…→【决策n】→【结束状态】这条链正是所有 DP 问题的统一模型从 base case 出发通过一次次决策推进状态最终得到目标状态的解。DP 与递归、迭代的关系动态规划离不开递推关系这与仓库中的 递归.md 一脉相承递归确定「递推公式 边界条件 bad case」而动态规划进一步要求「自底向上、缓存子问题结果」。自顶向下的递归带备忘录与自底向上的迭代是 DP 的两种实现路线纯递归运行效率较低存在函数调用开销递归次数过多还可能造成栈溢出DP 通过dp表或备忘录缓存已解子问题正是对递归的冗余计算进行剪枝。仓库中的 C 语言实现 fibonacci.c 同时给出了递归版fibonacci()与循环版fibonacci2()并在main()中调用clock()测量循环版计算 f(40) 的耗时直观体现了两种路线在性能上的差异可以作为本文案例的源码佐证。DP 的应用场景与问题特征如果一个问题可以把所有可能的答案穷举出来并且穷举后发现存在重叠子问题就可以考虑使用动态规划。使用动态规划算法的问题必须具备两个特征否则 DP 不具备优势子问题的重叠性不同子问题共享更小的子问题导致朴素递归重复计算最优子结构问题的最优解可以由子问题的最优解推导得到。动态规划的核心思想就是穷举求最值动态规划问题的一般形式就是求最值。动态规划本质上是运筹学的一种最优化方法只是在计算机问题上应用比较多。典型应用包括典型问题问题描述Fibonacci 数列递推基础问题代码参考 递归.md最大子数组和求连续子数组的最大和凑零钱问题给定面值求凑出目标金额的最少硬币数股票问题给定每日价格求最多 k 笔交易的最大收益打家劫舍问题num[i]代表第 i 个房子中的现金数目求能取出的最大金额约束是相邻房子的钱不能同时取出接雨水问题num[i]表示柱子高度计算下雨之后能接多少雨水青蛙跳阶问题一只青蛙一次可以跳 1 级或 2 级台阶求跳上 10 级台阶的总跳法数最小编辑距离求两个字符串互相转换所需的最少编辑操作次数最长递增子序列LIS如【567328】的最长递增子序列为【5678】输出长度 4最长公共子序列LCS求两个序列的最长公共子序列长度最长回文子序列求序列中最长的回文子序列长度0-1 背包问题给定容量与物品价值重量求能装下的最大价值青蛙跳阶问题DP 入门第一课以文档中详细展开的青蛙跳阶问题为例体会如何从问题描述中提炼递推关系想跳到第 10 级台阶要么先跳到第 9 级再跳 1 级上去要么先跳到第 8 级再一次迈 2 级上去。 同理想跳到第 9 级要么先到第 8 级再跳 1 级要么先到第 7 级再跳 2 级。 想跳到第 8 级要么先到第 7 级再跳 1 级要么先到第 6 级再跳 2 级。由此得到通用递推公式f(n) f(n-1) f(n-2)再确定边界条件bad case当只有 2 级台阶时有两种跳法直接跳两级或先跳一级再跳一级即f(2) 2当只有 1 级台阶时只有一种跳法即f(1) 1。于是问题转化为一个标准的 Fibonacci 型 DPdp[i] dp[i-1] dp[i-2]dp[1]1, dp[2]2自底向上递推即可完全对应 递归.md 中「确定递归公式 确定边界条件」的两步法。仓库 8 Algorithms Analysis/迭代法.md 中所说的「不断用旧值递推新值」的过程正是这种自底向上填表的过程。DP 与其他算法的边界分治、回溯、贪心DP VS 分治法与 分治算法.md 不同的是适合于用动态规划求解的问题经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题分解得到的子问题数目太多有些子问题被重复计算了很多次如果我们能保存已解决子问题的答案在需要时再找出来直接用就可以避免大量重复计算、节省时间实现上可以用一张表dp table记录所有已解的子问题的答案。分治算法.md 中明确列出分治的四个前提其中第四条「各个子问题相互独立如果这条不满足转为动态规划求解」正是二者分界的官方表述。仓库中 6 Sort/README.md 所对应的快速排序、归并排序等典型分治算法其子问题互不重叠因而分治适用一旦出现重叠子问题就应转向 DP。DP VS 回溯法DP 和回溯法都会用到递归但定位不同动态规划的暴力求解阶段就是回溯算法。有的问题具有重叠子问题性质可以用 dp table 或备忘录优化将递归树大幅剪枝这就变成了动态规划而有些问题没有重叠子问题就是 回溯法.md 所讲的回溯算法问题复杂度很高是不可避免的。回溯法也叫「试探法」是一种选优搜索法本质是 DFS 暴力穷举解空间常组织成树/图结构配合剪枝函数参见 回溯法.md 中的通用backtrack代码框架。判断一个递归问题能否用 DP 优化关键就是看它的递归树是否存在重叠子问题——这与 递归.md 中「画递归树可以很方便地看到是否存在重叠子问题如果有的话就可以采用动态规划」的建议完全吻合。补充DP 与贪心的区别贪心算法.md 指出贪心「不追求最优解只找到满意解」。与 DP 求最值不同贪心每一步做出当前看起来最优的局部选择不回退动态规划则穷举所有状态转移路径并取最值保证全局最优。这一区别在下一节「凑零钱问题」中有最直观的体现使用贪心策略并不能得到最优解。DP 解题模板四步走框架综合文档与 8 Algorithms Analysis/README.md 的算法分析思路DP 解题的基本步骤如下划分问题将原问题划分为一系列相互关联的子问题状态定义穷举「状态」确定 dp 数组/函数的含义并写好bad casebase case状态转移方程这一步最为困难暴力解法本身就是状态转移方程——先写出穷举所有选择的递归式再考虑用表缓存状态压缩若当前状态只与少数几个历史状态有关可压缩 dp 表维度以降低空间复杂度。对应通用伪代码模板# 初始化 base case dp[0][0][...] base # 进行状态转移 for 状态1 in 状态1的所有取值 for 状态2 in 状态2的所有取值 for ... dp[状态1][状态2][...] 求最值(选择1选择2...)外循环穷举所有状态内循环穷举所有选择——这就是绝大多数 DP 题目的代码骨架。下面用四大经典问题逐一演示这套流程。经典案例一最大子数组和示例输入nums [-2,1,-3,4,-1,2,1,-5,4]连续子数组[4,-1,2,1]的和最大输出6。解题流程状态定义dp[i]表示以nums[i]为结尾的「最大子数组和」dp[n-1]就是 nums 的「最大子数组和」状态转移dp[i] Math.max(nums[i], nums[i] dp[i - 1])—— 要么自成一派从 nums[i] 重新开始要么续上前面的子数组状态压缩注意到dp[i]仅仅和dp[i-1]的状态有关因此只需要两个变量滚动更新空间复杂度降为 O(1)。完整实现取自原文档public static int largestSubSequenceSum2(int[] nums){ int n nums.length; if (n 0) return 0; // base case int dp_0 nums[0]; int dp_1 0; int res dp_0; for (int i 1; i n; i) { // dp[i] max(nums[i], nums[i] dp[i-1]) dp_1 Math.max(nums[i], nums[i] dp_0); dp_0 dp_1; // 顺便计算最大的结果, 保存到 res res Math.max(res, dp_1); } return res; }要点解析dp_0/dp_1即滚动数组代替整个dp[]数组因为最大子数组和可能出现在任意下标处所以每轮都要用res记录历史最大值这个问题的递推思路与 递归.md 中「当前状态只和之前的两个状态有关只需存储之前的状态空间复杂度降为 O(1)」的优化技巧完全一致。经典案例二凑零钱问题问题给定面值 list1245710目标target 14求凑齐 14 元所需的最少零钱数量。为什么不能用贪心如果采用贪心策略每次都优先选最大面值并不能得到最优解——这正是 贪心算法.md 所警示的贪心只求满意解的典型案例。子问题分解思路要求amount 14时的最少硬币数只需利用已有的子问题结果知道凑出amount 13的最少硬币数子问题再加 1 个 1 元面值即可知道凑出amount 12的最少硬币数再加 1 个 2 元面值即可知道凑出amount 10的最少硬币数再加 1 个 4 元面值即可知道凑出amount 9的最少硬币数再加 1 个 5 元面值即可用递归视角描述即for (int coin : coins) { // 计算子问题的结果 int subProblem dp(coins, amount - coin); // 子问题无解则跳过 if (subProblem -1) continue; // 在子问题中选择最优解然后加一 res Math.min(res, subProblem 1); }通过备忘录dp 表消除重叠子问题不再使用递归而是用自底向上的 dp 数组。dp 数组的定义是当目标金额为 i 时至少需要dp[i]枚硬币凑出。推演dp[14]的填表过程dp[0] 0 dp[1] 1 dp[2] 1个2元的dp[1] 1个1元 ... dp[9] dp[8] 1个1元 dp[7] 1个2元 dp[5] 1个4元 dp[4] 1个5元dp[2] 1个7元 1 dp[i-coin] 从这些可选项里选择最小的核心转移代码//对于 dp[i], 遍历可选项, 选择最小的 for(int coin : coins) { if (i coin) { continue; } //dp[i] 保留最小的 dp[i] Math.min(dp[i],dp[i-coin] 1 ) }完整实现取自原文档//递归解法处理重叠子问题, 使用 dp[amount1] 备忘录 int coinChange2(int[] coins, int amount) { int[] dp new int[amount 1]; // 数组大小为 amount 1初始值也为 amount 1 // 为啥 dp 数组初始化为 amount 1 呢? // 因为凑成 amount 金额的硬币数最多只可能等于 amount全用 1 元面值的硬币所以初始化为 amount 1 就相当于初始化为正无穷 Arrays.fill(dp, amount 1); // base case dp[0] 0; // 外层 for 循环在遍历所有状态的所有取值 for (int i 0; i dp.length; i) { // 内层 for 循环在求所有选择的最小值 for (int coin : coins) { // 子问题无解跳过 if (i - coin 0) { continue; } dp[i] Math.min(dp[i], 1 dp[i - coin]); } } return (dp[amount] amount 1) ? -1 : dp[amount]; }实现细节解读初始化技巧dp数组初始值设为amount 1相当于正无穷因为凑成amount金额最多只需要amount枚硬币全用 1 元面值任何大于该值的数都代表不可达无解判断最终dp[amount] amount 1说明无法凑出目标金额返回-1这个案例完整演示了「暴力递归 → 备忘录 → 自底向上 dp 表」的进化路径正是文档所述「暴力解法就是状态转移方程」的最佳注脚。经典案例三股票问题问题num[i]表示第 i 天的股票价格设计一个算法交易策略计算你能获得的最大收益最多可以完成 k 笔交易。示例[3,2,6,5,1,3]k1第 2 天以 2 元买入第 3 天以 6 元卖出利润6-2 4元是最大利润k2可以交易 2 次[2,6][1,3]两段买卖组成最大利润。按四步走框架分析状态定义需要三个维度才能完整刻画一个决策状态——「第几天 i」「手上是否持股持有 / 空仓」「已经完成的交易次数 k」。因此 dp 数组通常是三维的dp[i][k][0/1]表示第 i 天、剩余交易次数上限为 k、当前持有1或未持有0股票时的最大收益状态转移每天的收益由两个方向递推而来——今天空仓 max(昨天空仓不动, 昨天持有 今天卖出获利)今天持有 max(昨天持有不动, 昨天空仓 - 今天买入花费)状态压缩第 i 天的状态只依赖第 i-1 天可以只保留前一天的持有/空仓两个变量滚动更新把二维表压成 O(1) 空间。从源码结构看文档将该问题拆解为「状态定义 / 状态转移 / 状态压缩」三个小节并预留了代码位说明这是一个非常适合训练 DP 建模能力的高频面试题难点不在于递推本身而在于如何设计出完备的状态维度。建议读者按照上面的三维状态定义自行补全实现并与「打家劫舍」「背包问题」对照体会状态越多越要依赖模板穷举的规律。经典案例四接雨水问题问题num[i]表示柱子高度计算下雨之后最多能接多少雨水。核心洞察位置 i 能接多少水取决于它两侧的墙位置 i 能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关分别称这两个柱子高度为l_max和r_max位置 i 最大的水柱高度就是min(l_max, r_max)若该值高于num[i]则位置 i 可蓄水min(l_max, r_max) - num[i]累加所有位置即得答案。三种经典解法递进对应文档中列出的思路暴力解法对每个位置 i向左向右各扫描一遍求l_max、r_max时间复杂度 O(n²)备忘录解法预先从左到右、从右到左各遍历一次分别用l_max[]、r_max[]两个数组记录每个位置两侧的最高柱子再单次遍历累加蓄水量时间复杂度 O(n)、空间复杂度 O(n)——这正是 DP 的以空间换时间、存储中间状态思想的直接应用双指针解法进一步状态压缩——用左右两个指针从两端向中间收缩只需维护当前左侧最高值和右侧最高值谁矮就先结算谁所在位置的蓄水量时间复杂度 O(n)、空间复杂度 O(1)。这三种解法是绝佳的进阶练习同一个问题从暴力到备忘录再到双指针恰好完整走完了「状态定义 → 缓存子问题 → 状态压缩」的 DP 进化路线与 迭代法.md 所述用旧值递推新值、控制迭代过程的过程一一对应。其他高频 DP 题型速览除上述四大案例外文档还列举了以下常见题型均可按「状态定义 转移方程 压缩」模板切入打家劫舍dp[i] max(dp[i-1], dp[i-2] num[i])——相邻约束下取最大值最小编辑距离二维 dp状态为两个字符串的前缀长度转移含增、删、改三种操作最长递增子序列LISdp[i]表示以第 i 个元素结尾的最长递增子序列长度双层循环转移最长公共子序列LCS二维 dp字符相等与不等分别转移最长回文子序列区间 DP状态为子序列的起止下标0-1 背包问题dp[i][w]表示前 i 件物品在容量 w 下的最大价值是二维状态 选择装/不装的经典代表。这些题目与本文四大案例共享同一套模板建议读者在仓库的 9 Algorithms Job Interview 目录下结合 C 语言面试题源码如 factorial.c 的递归阶乘、fibonacci.c 的递归与循环对照进行练习理解递归公式 边界条件如何一步步转化为可运行的 dp 代码。总结一份 DP 自查清单在实战中请始终按以下顺序自问自答能否穷举所有解能则继续穷举时是否存在重叠子问题存在DP 才适用不存在回归回溯/分治最优解能否由子问题最优解组合得出最优子结构是则确定状态状态有哪些维度写出 dp 数组或 dp 函数的完整签名base case 是什么先填边界状态转移方程是什么即穷举所有选择求最值的暴力递推式能否状态压缩观察当前状态仅依赖哪些历史状态尝试滚动变量。掌握这套流程配合本文四个完整案例的代码演练即可应对绝大多数动态规划面试题。若需进一步对照算法分析总览可参考 8 Algorithms Analysis/README.md分治与回溯的边界辨析可分别查阅 分治算法.md 与 回溯法.md。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐Hello 算法动态规划解题框架从题目识别到状态转移方程与空间优化的完整方法论Hello 算法动态规划解题框架从题目识别到状态转移方程与空间优化的完整方法论 动态规划Dynamic Programming, DP是算法面试与工程优化教程文档示例工程教育FreeCAD免费3D参数化建模完全指南从第一个零件到结构分析一次学会FreeCAD免费3D参数化建模完全指南从第一个零件到结构分析一次学会 FreeCAD 是一款完全免费、开源的跨平台 3D 参数化建模软件面向机械工程师、桌面应用3D建模图形学工业制造UFO AppAgent 七状态有限状态机深度解析从状态定义到转移控制的完整实现指南UFO AppAgent 七状态有限状态机深度解析从状态定义到转移控制的完整实现指南 UFOUser Focused Agent中的 AppAgent 是人工智能AI Agent自主智能体GUI 自动化Agent 编排多智能体RAG上一篇开源相控阵雷达完整指南三步跑通 10.5GHz PLFM 雷达系统下一篇如何设计dive-into-machine-learning开源商业模式社区版与企业版产品策略完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考