1. 项目概述从“最优子结构”到“状态转移方程”动态规划这四个字在算法领域的分量足以让无数初学者望而生畏也让许多资深工程师将其视为解决复杂优化问题的“银弹”。我第一次接触这个概念是在解决一个看似简单的“爬楼梯”问题时——每次可以爬1或2个台阶爬到第n阶有多少种方法用递归暴力求解当n40时程序已经慢得令人发指。直到我理解了动态规划的核心思想用几行代码和一个数组瞬间就得到了结果。那一刻的顿悟让我意识到这不仅仅是一个算法更是一种强大的数学建模和问题拆解思维。简单来说动态规划是一种用于求解多阶段决策过程最优化问题的数学方法。它的核心魅力在于能够将一个大问题分解为一系列相互关联的小问题并通过保存子问题的解来避免重复计算从而极大地提升效率。无论是计算最短路径、资源分配还是游戏AI的决策制定其背后往往都有动态规划的身影。它解决的正是那些具有“重叠子问题”和“最优子结构”特性的难题——当你发现一个问题可以分解且子问题的最优解能构成原问题的最优解时动态规划就该登场了。这篇文章我将结合自己处理过的“最长上升子序列”、“背包问题”等经典案例以及一些工程中的实际场景为你彻底拆解动态规划。我不会只给你枯燥的定义和公式而是会带你走过我踩过的坑、总结的心得让你理解为什么要设计状态、如何找到状态转移方程、以及怎样优化空间复杂度。无论你是正在备战技术面试的学生还是希望提升问题解决能力的开发者相信这套从原理到实战的完整心法都能让你对动态规划有一个全新的、透彻的认识。2. 核心思想拆解重叠子问题与最优子结构动态规划之所以高效其根基在于两个核心性质重叠子问题和最优子结构。理解这两个性质是判断一个问题能否用动态规划解决以及如何设计解法的关键第一步。2.1 最优子结构大问题的最优解包含小问题的最优解这是动态规划可行的前提。如果一个问题的最优解可以通过组合其子问题的最优解来获得那么我们就说该问题具有最优子结构。一个生活化的类比假设你要从北京开车到上海并希望找到最短路径。如果“北京到上海的最短路径”必然经过济南那么这条路径一定由“北京到济南的最短路径”和“济南到上海的最短路径”组成。你不会在“北京到济南”这一段选择一条更长的路因为那会导致整体路径变长。这里“北京到上海”这个大问题的最优解最短路径依赖于“北京到济南”和“济南到上海”这两个子问题的最优解。在算法中的体现以经典的“最长上升子序列”问题为例。给定一个数列[10, 9, 2, 5, 3, 7, 101, 18]我们需要找到其中最长的严格递增子序列的长度。假设我们定义dp[i]为以第i个数字结尾的最长上升子序列的长度。那么为了求dp[i]我们需要检查所有在i之前的j(j i)。如果nums[j] nums[i]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的子序列。此时dp[i]的最优解最大值必然来自于某个dp[j] 1的最大值。这里dp[i]这个子问题的最优解是由前面一系列子问题dp[j]的最优解推导而来的。这就是最优子结构。注意最优子结构是问题本身的属性不是动态规划独有的。贪心算法也要求最优子结构但动态规划在处理时子问题之间会有重叠。2.2 重叠子问题递归树的重复计算陷阱这是动态规划提升效率的关键。在直接使用递归如分治法解决具有最优子结构的问题时递归树中会反复计算完全相同的子问题造成指数级的时间浪费。以斐波那契数列为例F(n) F(n-1) F(n-2)。如果我们递归计算F(5)过程如下F(5) F(4) F(3) (F(3)F(2)) (F(2)F(1)) ((F(2)F(1))(F(1)F(0))) ((F(1)F(0))F(1))可以看到F(3)、F(2)、F(1)都被计算了多次。F(2)被计算了3次。当 n 很大时这种重复计算是灾难性的时间复杂度为 O(2^n)。动态规划的解决方案既然这些子问题被重复计算我们何不“记住”它们的答案我们创建一个数组dpdp[i]表示F(i)的值。计算过程变为初始化dp[0]0, dp[1]1。从i2开始循环到ndp[i] dp[i-1] dp[i-2]。 这样每个子问题F(i)只被计算一次结果保存在dp[i]中供后续使用时间复杂度骤降至 O(n)。这个“记住答案”的过程就是“记忆化搜索”或“制表法”是动态规划的核心操作之一。实操心得当你面对一个新问题时先尝试画出递归树哪怕是在脑海里。如果发现树中有大量相同的节点子问题那么这个问题很可能具有重叠子问题动态规划就能派上用场。一个快速的判断方法是写出递归函数后看看是否有很多参数相同的递归调用。3. 动态规划的解题框架与状态设计理解了核心思想后我们需要一套可操作的解题框架。动态规划解题通常遵循一个清晰的四步法而其中最核心、也最考验功力的就是状态设计。3.1 标准四步法定义状态、确定转移、初始化、计算顺序定义状态 (Define the State) 这是最重要的一步决定了整个算法的成败。状态就是我们需要“记住”的东西通常用一个或多个维度的数组dp表来表示。状态的定义必须能够完整描述一个子问题。常见形式dp[i]表示以第i个元素结尾的某种最优值dp[i][j]表示在第一个序列的前i个元素和第二个序列的前j个元素之间的某种最优值如编辑距离dp[i][w]表示考虑前i件物品在背包容量为w时的最大价值。设计原则状态的定义要能让你从已知状态推导出未知状态。通常状态参数就是问题中会变化的量。确定状态转移方程 (State Transition Equation) 这是动态规划的灵魂是数学归纳法的递推式。它描述了如何通过已知的、更小的子问题状态最优解来计算出当前状态的最优解。思考方式“要得到dp[i]我需要哪些已经计算好的dp[j](j i)” 或者 “在做出某个决策选或不选匹配或不匹配后状态如何变化”举例爬楼梯状态dp[i]表示爬到第i阶台阶的方法总数。要爬到第i阶你只能从第i-1阶爬1步上来或者从第i-2阶爬2步上来。因此dp[i] dp[i-1] dp[i-2]。初始化 (Initialization) 状态转移方程决定了递推的“链条”而初始化则是这个链条的起点。必须正确设置最小子问题边界条件的解否则整个推导将无法进行或得出错误结果。举例在爬楼梯问题中dp[1] 1(一种方法爬1步)dp[2] 2(两种方法11 或 直接2步)。有时初始化可能需要考虑更多边界比如dp[0] 1表示空集也是一种方案在组合问题中常见。确定计算顺序 (Order of Computation) 我们需要确保在计算一个状态dp[i]时它所依赖的所有子状态如dp[i-1],dp[i-2]都已经被计算并存储好了。这通常决定了我们循环的嵌套顺序。自底向上 (Bottom-up)最常见的“制表法”。我们从最小的子问题开始逐步循环计算到原问题。例如计算斐波那契数列就是从i2循环到n。自顶向下 (Top-down)即“记忆化搜索”。我们用递归函数尝试解决问题但在函数开头检查结果是否已缓存在dp表中如果没有则计算并缓存。这种方式更符合思维惯性但可能有递归栈开销。3.2 状态设计的艺术以“01背包问题”为例“01背包问题”是理解状态设计的绝佳例子。问题描述有N件物品和一个容量为W的背包。第i件物品的重量是weight[i]价值是value[i]。每件物品只能选或不选0或1求解将哪些物品装入背包可使总价值最大且不超过背包容量。如何设计状态识别变化量在决策过程中什么在变一是我们“考虑的物品范围”从前1件到前2件...直到前N件二是“背包剩余的容量”从W到0。这两个维度共同决定了当前子问题的局面。定义状态因此我们定义一个二维数组dp[i][c]。其含义是考虑前i件物品物品编号从1到N在背包容量恰好为c的情况下可以获取的最大价值。这里“考虑前i件物品”意味着我们只在这i件物品里做选择不一定全部装入。“容量恰好为c”是一个关键点有时也定义为“容量不超过c”两种定义对应的初始化略有不同但核心转移思想一致。状态转移方程 对于第i件物品我们只有两种选择不选它那么问题就退化成了“考虑前i-1件物品容量为c”的子问题。最大价值就是dp[i-1][c]。选它前提是背包能装下即c weight[i]。如果选了背包容量会消耗weight[i]价值增加value[i]。那么剩余的局面就是“考虑前i-1件物品容量为c - weight[i]”的子问题。总价值为dp[i-1][c - weight[i]] value[i]。 我们的目标是价值最大所以在这两种决策中取最大值dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])其中第二个选项仅在c weight[i]时有效。初始化dp[0][c] 0考虑0件物品无论容量多大价值都是0。对于“容量恰好为c”的定义通常dp[i][0] 0容量为0装不下任何物品价值为0。如果定义为“容量不超过c”则dp[i][0]也为0。计算顺序 显然计算dp[i][c]需要用到dp[i-1][...]的数据。因此外层循环从小到大遍历物品i从1到N内层循环从小到大遍历容量c从0到W即可。这样当计算dp[i][c]时dp[i-1][c]和dp[i-1][c-weight[i]]都已经是计算好的值。这个设计为什么有效因为它完美刻画了决策过程的所有可能性并将重叠子问题例如不同的物品组合可能达到相同的剩余容量和相似的价值通过dp表存储起来避免了重复枚举所有2^N种组合的暴力搜索。4. 经典问题深度剖析与空间优化掌握了框架我们通过两个经典问题来深化理解并探讨一个重要的高级技巧空间优化。4.1 案例一最长上升子序列的两种视角问题给定一个整数数组nums找到其中最长严格递增子序列的长度。解法1标准动态规划状态定义dp[i]表示以nums[i]结尾的最长上升子序列的长度。转移方程对于每个i遍历所有j i。如果nums[j] nums[i]说明nums[i]可以接在nums[j]后面。那么dp[i]可能是dp[j] 1。我们需要取所有可能中的最大值dp[i] max(dp[i], dp[j] 1)对所有j i且nums[j] nums[i]。初始化每个位置至少可以以自己开头长度为1所以dp[i] 1。答案最终结果是dp数组中的最大值因为最长子序列可能以任何一个位置结尾。复杂度时间复杂度 O(n²)空间复杂度 O(n)。解法2贪心二分查找优化到 O(n log n)这是动态规划思想结合其他技巧的经典优化展示了算法设计的灵活性。状态重新定义我们维护一个数组tailstails[k]的值代表长度为k1的所有上升子序列中结尾元素的最小值。这个数组本身是严格递增的可以用反证法证明。过程遍历nums中的每个数x。如果x大于tails中的所有元素即大于最后一个元素说明我们可以得到一个更长的上升子序列将x追加到tails末尾。否则我们在tails数组中找到第一个大于等于x的元素tails[i]并用x替换它。因为tails是递增的可以用二分查找复杂度 O(log n)。为什么可以替换替换tails[i]为更小的x意味着未来有更大的机会接上其他数字从而可能获得更长的子序列。它并没有改变当前tails的长度但优化了潜在的结构。答案遍历结束后tails的长度就是最长上升子序列的长度。本质这种方法可以理解为在动态规划dp数组的基础上额外维护了一个关于“结尾最小值”的贪心策略并利用其单调性进行二分加速。它求出的长度是正确的但tails数组本身不一定是最长上升子序列的真实序列。实操心得面试中如果被问到最长上升子序列先给出 O(n²) 的动态规划解法是稳妥的。如果面试官追问优化再引出这种 O(n log n) 的巧妙解法会大大加分。关键在于理解tails数组含义的转变——从存储“长度”变为存储“特定长度下的最小结尾”。4.2 案例二01背包问题的空间优化滚动数组回顾我们定义的二维状态dp[i][c]。观察状态转移方程dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])。你会发现计算第i行的数据时只依赖于第i-1行的数据。也就是说我们并不需要保存从0到i-2的所有历史数据。空间优化技巧滚动数组我们可以只用一个一维数组dp[c]来表示“容量为c时的最大价值”。在计算过程中我们从后向前遍历容量c。初始时dp[c]代表i0没有物品时的状态全部为0。当我们处理第i件物品时这个一维数组dp在逻辑上还保存着i-1件物品时的结果。对于容量c从W遍历到weight[i]必须逆序我们执行dp[c] max(dp[c], dp[c - weight[i]] value[i])dp[c]等号右边对应二维情况下不选第i件物品的方案即dp[i-1][c]。因为dp[c]还没有被本轮更新它存储的就是上一轮i-1的结果。dp[c - weight[i]] value[i]对应二维情况下选择第i件物品的方案即dp[i-1][c-weight[i]] value[i]。因为c是从大到小遍历的所以当计算dp[c]时dp[c-weight[i]]也一定是上一轮i-1的结果没有被本轮修改过。为什么必须逆序这是关键如果顺序遍历c从weight[i]到W会怎样假设weight[i]2, value[i]5。计算dp[2] max(dp[2], dp[0]5) 5。此时dp[2]被更新为5代表考虑了第i件物品。接着计算dp[4] max(dp[4], dp[2]5)。注意这里的dp[2]已经是本轮更新后的值5了这意味着dp[4] max(..., 5510)相当于第i件物品被重复计算了两次因为dp[2]已经包含了一件物品i再加5就变成了两件。这完全违背了“01背包”每件物品只能选一次的原则。 逆序遍历保证了在计算dp[c]时它所依赖的dp[c-weight[i]]是“纯净”的、未被本轮物品污染过的状态。优化结果空间复杂度从 O(N*W) 降为 O(W)。这是一个非常显著的优化尤其当物品数量N很大时。注意事项滚动数组优化是动态规划中一个非常经典的技巧但并非所有问题都适用。它适用于当前状态只依赖于上一行或前几行状态的情况。在应用时务必仔细分析依赖关系确定遍历顺序正序、逆序、甚至更复杂的顺序否则极易出错。我个人的习惯是先写出清晰的二维DP确认逻辑无误后再考虑是否可以以及如何进行空间优化。5. 动态规划的变种与常见问题模式动态规划不是一个死板的算法而是一个框架。很多问题可以通过巧妙的建模转化为动态规划问题。以下是一些常见的模式5.1 区间动态规划这类问题通常涉及对一个序列或区间进行一系列操作求最优解。状态定义往往与区间有关。典型问题矩阵连乘、石子合并、最长回文子串。状态设计通常定义dp[i][j]表示区间[i, j]上的最优解。转移方程通常需要枚举区间分割点k(i k j)将大区间[i, j]分解为两个子区间[i, k]和[k1, j]然后合并子问题的解。例如石子合并问题dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j))其中sum(i,j)是合并区间[i,j]的代价。计算顺序由于计算大区间需要用到更小的区间所以通常按照区间长度从小到大进行循环。5.2 状态压缩动态规划当状态中的某些维度是布尔值或状态数很少时可以用一个整数的二进制位来表示状态从而压缩空间。典型问题旅行商问题、棋盘覆盖问题如用1*2骨牌覆盖网格。状态设计例如在旅行商问题中需要记录已经访问过哪些城市。如果有n个城市可以用一个n位的二进制数mask表示第i位为1表示城市i已访问。状态可以定义为dp[mask][i]表示从起点出发访问了mask表示的城市集合最后停留在城市i的最小花费。优势与难点极大地减少了状态表示的空间但代码可读性会下降需要熟练运用位运算如(mask i) 1检查第i位mask | (1 i)设置第i位。5.3 树形动态规划在树形结构如公司层级、决策树上进行动态规划。通常需要递归地进行后序遍历。典型问题二叉树中的最大路径和、公司派对的最大快乐值、没有上司的舞会。状态设计通常为每个节点设计一个状态数组。例如在“没有上司的舞会”中可以为每个员工节点u定义dp[u][0]员工u不参加舞会时以其为根的子树能获得的最大快乐值。dp[u][1]员工u参加舞会时以其为根的子树能获得的最大快乐值。转移方程根据父子关系构建。dp[u][0] sum( max(dp[v][0], dp[v][1]) )v是u的子节点。u不参加子节点可参加可不参加。dp[u][1] happy[u] sum( dp[v][0] )。u参加则子节点都不能参加。5.4 数位动态规划用于解决与数字的数位个、十、百...相关的计数或求值问题。典型问题统计区间[L, R]内满足某种条件如不含数字4或各位数字之和为特定值的数字个数。核心思想将数字按位拆解逐位决策。状态通常包括当前处理到第几位 (pos)、前几位是否已经小于上限 (limit)、前导零状态 (lead)、以及根据题目要求需要的其他状态如各位数字之和sum、前一位数字pre等。实现方式通常采用记忆化搜索DFS 记忆化来实现比迭代循环更直观。6. 实战调试与思维训练指南理论懂了但一写就错这是学习动态规划的正常阶段。下面分享一些调试技巧和提升思维的方法。6.1 调试技巧打印DP表与手算小规模案例动态规划的bug往往隐藏在状态定义或转移方程的细节中。最有效的调试方法就是打印出整个DP表并与你手算的小规模结果进行对比。操作步骤构造最小可复现案例不要一上来就用复杂的测试用例。用一个足够小、你大脑能完全模拟的输入。例如对于背包问题用2-3件物品容量为5。手动推导在纸上画出二维表格根据你的状态定义和转移方程一步步填满这个表格。这是检验你思路是否清晰的终极标准。程序输出在你的代码中在计算完DP表后将其完整打印出来格式化对齐更好。逐格对比将程序输出的表格与你手算的表格进行逐格对比。第一个出现差异的格子就是你的bug所在。仔细检查这个格子的计算过程它依赖的前状态对吗转移方程写对了吗边界条件数组越界考虑到了吗常见错误点检查清单数组大小dp数组的长度是否足够通常是n1或W1因为0下标常用来表示边界。初始化dp[0][...]和dp[...][0]初始化对了吗是否符合状态定义循环范围i和c的循环是从0开始还是1开始结束条件是否正确还是状态转移条件在状态转移前是否检查了前置条件如背包容量是否足够c weight[i]如果条件不满足应该怎么处理通常是直接继承dp[i-1][c]顺序问题如果使用了滚动数组优化遍历顺序尤其是内层容量循环是否正确是正序还是逆序6.2 思维训练如何培养“动态规划思维”看到新问题如何想到用动态规划这需要刻意练习。识别问题特征求最值最大值、最小值、最长、最短、最多方案数等。计数问题有多少种方式、多少种路径等。可行性问题是否存在某种方案。同时问题可以被分解为规模更小的相似子问题。尝试暴力搜索先思考最暴力的解法如递归、回溯枚举所有可能。在思考暴力解的过程中你自然会发现很多重复的计算路径。这些重复的路径就是“重叠子问题”的线索。定义“状态”问自己“在暴力搜索的过程中是什么参数在决定当前的局面” 这些参数通常就是状态的定义。例如在背包问题中是“当前考虑到第几个物品”和“剩余容量”在矩阵路径中是“当前坐标”。寻找“选择”与“转移”在当前状态下你可以做出哪些“选择”比如选或不选往左走还是往右走做出每个选择后状态会如何变化这个变化关系就是状态转移方程。从简单问题开始刷题按照专题和难度循序渐进。一个经典的路线是入门斐波那契、爬楼梯、最小路径和。基础不同路径、01背包、完全背包、最长上升子序列。进阶打家劫舍系列、股票买卖系列、子序列问题编辑距离、最长公共子序列。提高区间DP、状态压缩DP、树形DP。我个人最受用的一个习惯是每解决一道动态规划问题不仅写出代码还要用文字在注释或笔记中清晰地复述以下内容1) 状态定义2) 状态转移方程及推导理由3) 初始化4) 计算顺序5) 最终答案在哪。这个过程能极大地加深理解形成肌肉记忆。动态规划确实有门槛但一旦跨越你会发现很多复杂的优化问题都变得有迹可循。它更像是一种将问题“结构化”的思维工具而不仅仅是算法模板。多思考“为什么这样定义状态”比死记硬背十道题的代码更有价值。当你再遇到类似“最长上升子序列”或“背包”的变种时你就能从容地分析变化设计出属于自己的状态和方程了。 
长河君 · 2026/8/29 2:02:04 · 阅读 1.2k 动态规划核心思想与实战：从最优子结构到状态转移方程
1. 项目概述从“最优子结构”到“状态转移方程”动态规划这四个字在算法领域的分量足以让无数初学者望而生畏也让许多资深工程师将其视为解决复杂优化问题的“银弹”。我第一次接触这个概念是在解决一个看似简单的“爬楼梯”问题时——每次可以爬1或2个台阶爬到第n阶有多少种方法用递归暴力求解当n40时程序已经慢得令人发指。直到我理解了动态规划的核心思想用几行代码和一个数组瞬间就得到了结果。那一刻的顿悟让我意识到这不仅仅是一个算法更是一种强大的数学建模和问题拆解思维。简单来说动态规划是一种用于求解多阶段决策过程最优化问题的数学方法。它的核心魅力在于能够将一个大问题分解为一系列相互关联的小问题并通过保存子问题的解来避免重复计算从而极大地提升效率。无论是计算最短路径、资源分配还是游戏AI的决策制定其背后往往都有动态规划的身影。它解决的正是那些具有“重叠子问题”和“最优子结构”特性的难题——当你发现一个问题可以分解且子问题的最优解能构成原问题的最优解时动态规划就该登场了。这篇文章我将结合自己处理过的“最长上升子序列”、“背包问题”等经典案例以及一些工程中的实际场景为你彻底拆解动态规划。我不会只给你枯燥的定义和公式而是会带你走过我踩过的坑、总结的心得让你理解为什么要设计状态、如何找到状态转移方程、以及怎样优化空间复杂度。无论你是正在备战技术面试的学生还是希望提升问题解决能力的开发者相信这套从原理到实战的完整心法都能让你对动态规划有一个全新的、透彻的认识。2. 核心思想拆解重叠子问题与最优子结构动态规划之所以高效其根基在于两个核心性质重叠子问题和最优子结构。理解这两个性质是判断一个问题能否用动态规划解决以及如何设计解法的关键第一步。2.1 最优子结构大问题的最优解包含小问题的最优解这是动态规划可行的前提。如果一个问题的最优解可以通过组合其子问题的最优解来获得那么我们就说该问题具有最优子结构。一个生活化的类比假设你要从北京开车到上海并希望找到最短路径。如果“北京到上海的最短路径”必然经过济南那么这条路径一定由“北京到济南的最短路径”和“济南到上海的最短路径”组成。你不会在“北京到济南”这一段选择一条更长的路因为那会导致整体路径变长。这里“北京到上海”这个大问题的最优解最短路径依赖于“北京到济南”和“济南到上海”这两个子问题的最优解。在算法中的体现以经典的“最长上升子序列”问题为例。给定一个数列[10, 9, 2, 5, 3, 7, 101, 18]我们需要找到其中最长的严格递增子序列的长度。假设我们定义dp[i]为以第i个数字结尾的最长上升子序列的长度。那么为了求dp[i]我们需要检查所有在i之前的j(j i)。如果nums[j] nums[i]说明nums[i]可以接在nums[j]结尾的子序列后面形成一个更长的子序列。此时dp[i]的最优解最大值必然来自于某个dp[j] 1的最大值。这里dp[i]这个子问题的最优解是由前面一系列子问题dp[j]的最优解推导而来的。这就是最优子结构。注意最优子结构是问题本身的属性不是动态规划独有的。贪心算法也要求最优子结构但动态规划在处理时子问题之间会有重叠。2.2 重叠子问题递归树的重复计算陷阱这是动态规划提升效率的关键。在直接使用递归如分治法解决具有最优子结构的问题时递归树中会反复计算完全相同的子问题造成指数级的时间浪费。以斐波那契数列为例F(n) F(n-1) F(n-2)。如果我们递归计算F(5)过程如下F(5) F(4) F(3) (F(3)F(2)) (F(2)F(1)) ((F(2)F(1))(F(1)F(0))) ((F(1)F(0))F(1))可以看到F(3)、F(2)、F(1)都被计算了多次。F(2)被计算了3次。当 n 很大时这种重复计算是灾难性的时间复杂度为 O(2^n)。动态规划的解决方案既然这些子问题被重复计算我们何不“记住”它们的答案我们创建一个数组dpdp[i]表示F(i)的值。计算过程变为初始化dp[0]0, dp[1]1。从i2开始循环到ndp[i] dp[i-1] dp[i-2]。 这样每个子问题F(i)只被计算一次结果保存在dp[i]中供后续使用时间复杂度骤降至 O(n)。这个“记住答案”的过程就是“记忆化搜索”或“制表法”是动态规划的核心操作之一。实操心得当你面对一个新问题时先尝试画出递归树哪怕是在脑海里。如果发现树中有大量相同的节点子问题那么这个问题很可能具有重叠子问题动态规划就能派上用场。一个快速的判断方法是写出递归函数后看看是否有很多参数相同的递归调用。3. 动态规划的解题框架与状态设计理解了核心思想后我们需要一套可操作的解题框架。动态规划解题通常遵循一个清晰的四步法而其中最核心、也最考验功力的就是状态设计。3.1 标准四步法定义状态、确定转移、初始化、计算顺序定义状态 (Define the State) 这是最重要的一步决定了整个算法的成败。状态就是我们需要“记住”的东西通常用一个或多个维度的数组dp表来表示。状态的定义必须能够完整描述一个子问题。常见形式dp[i]表示以第i个元素结尾的某种最优值dp[i][j]表示在第一个序列的前i个元素和第二个序列的前j个元素之间的某种最优值如编辑距离dp[i][w]表示考虑前i件物品在背包容量为w时的最大价值。设计原则状态的定义要能让你从已知状态推导出未知状态。通常状态参数就是问题中会变化的量。确定状态转移方程 (State Transition Equation) 这是动态规划的灵魂是数学归纳法的递推式。它描述了如何通过已知的、更小的子问题状态最优解来计算出当前状态的最优解。思考方式“要得到dp[i]我需要哪些已经计算好的dp[j](j i)” 或者 “在做出某个决策选或不选匹配或不匹配后状态如何变化”举例爬楼梯状态dp[i]表示爬到第i阶台阶的方法总数。要爬到第i阶你只能从第i-1阶爬1步上来或者从第i-2阶爬2步上来。因此dp[i] dp[i-1] dp[i-2]。初始化 (Initialization) 状态转移方程决定了递推的“链条”而初始化则是这个链条的起点。必须正确设置最小子问题边界条件的解否则整个推导将无法进行或得出错误结果。举例在爬楼梯问题中dp[1] 1(一种方法爬1步)dp[2] 2(两种方法11 或 直接2步)。有时初始化可能需要考虑更多边界比如dp[0] 1表示空集也是一种方案在组合问题中常见。确定计算顺序 (Order of Computation) 我们需要确保在计算一个状态dp[i]时它所依赖的所有子状态如dp[i-1],dp[i-2]都已经被计算并存储好了。这通常决定了我们循环的嵌套顺序。自底向上 (Bottom-up)最常见的“制表法”。我们从最小的子问题开始逐步循环计算到原问题。例如计算斐波那契数列就是从i2循环到n。自顶向下 (Top-down)即“记忆化搜索”。我们用递归函数尝试解决问题但在函数开头检查结果是否已缓存在dp表中如果没有则计算并缓存。这种方式更符合思维惯性但可能有递归栈开销。3.2 状态设计的艺术以“01背包问题”为例“01背包问题”是理解状态设计的绝佳例子。问题描述有N件物品和一个容量为W的背包。第i件物品的重量是weight[i]价值是value[i]。每件物品只能选或不选0或1求解将哪些物品装入背包可使总价值最大且不超过背包容量。如何设计状态识别变化量在决策过程中什么在变一是我们“考虑的物品范围”从前1件到前2件...直到前N件二是“背包剩余的容量”从W到0。这两个维度共同决定了当前子问题的局面。定义状态因此我们定义一个二维数组dp[i][c]。其含义是考虑前i件物品物品编号从1到N在背包容量恰好为c的情况下可以获取的最大价值。这里“考虑前i件物品”意味着我们只在这i件物品里做选择不一定全部装入。“容量恰好为c”是一个关键点有时也定义为“容量不超过c”两种定义对应的初始化略有不同但核心转移思想一致。状态转移方程 对于第i件物品我们只有两种选择不选它那么问题就退化成了“考虑前i-1件物品容量为c”的子问题。最大价值就是dp[i-1][c]。选它前提是背包能装下即c weight[i]。如果选了背包容量会消耗weight[i]价值增加value[i]。那么剩余的局面就是“考虑前i-1件物品容量为c - weight[i]”的子问题。总价值为dp[i-1][c - weight[i]] value[i]。 我们的目标是价值最大所以在这两种决策中取最大值dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])其中第二个选项仅在c weight[i]时有效。初始化dp[0][c] 0考虑0件物品无论容量多大价值都是0。对于“容量恰好为c”的定义通常dp[i][0] 0容量为0装不下任何物品价值为0。如果定义为“容量不超过c”则dp[i][0]也为0。计算顺序 显然计算dp[i][c]需要用到dp[i-1][...]的数据。因此外层循环从小到大遍历物品i从1到N内层循环从小到大遍历容量c从0到W即可。这样当计算dp[i][c]时dp[i-1][c]和dp[i-1][c-weight[i]]都已经是计算好的值。这个设计为什么有效因为它完美刻画了决策过程的所有可能性并将重叠子问题例如不同的物品组合可能达到相同的剩余容量和相似的价值通过dp表存储起来避免了重复枚举所有2^N种组合的暴力搜索。4. 经典问题深度剖析与空间优化掌握了框架我们通过两个经典问题来深化理解并探讨一个重要的高级技巧空间优化。4.1 案例一最长上升子序列的两种视角问题给定一个整数数组nums找到其中最长严格递增子序列的长度。解法1标准动态规划状态定义dp[i]表示以nums[i]结尾的最长上升子序列的长度。转移方程对于每个i遍历所有j i。如果nums[j] nums[i]说明nums[i]可以接在nums[j]后面。那么dp[i]可能是dp[j] 1。我们需要取所有可能中的最大值dp[i] max(dp[i], dp[j] 1)对所有j i且nums[j] nums[i]。初始化每个位置至少可以以自己开头长度为1所以dp[i] 1。答案最终结果是dp数组中的最大值因为最长子序列可能以任何一个位置结尾。复杂度时间复杂度 O(n²)空间复杂度 O(n)。解法2贪心二分查找优化到 O(n log n)这是动态规划思想结合其他技巧的经典优化展示了算法设计的灵活性。状态重新定义我们维护一个数组tailstails[k]的值代表长度为k1的所有上升子序列中结尾元素的最小值。这个数组本身是严格递增的可以用反证法证明。过程遍历nums中的每个数x。如果x大于tails中的所有元素即大于最后一个元素说明我们可以得到一个更长的上升子序列将x追加到tails末尾。否则我们在tails数组中找到第一个大于等于x的元素tails[i]并用x替换它。因为tails是递增的可以用二分查找复杂度 O(log n)。为什么可以替换替换tails[i]为更小的x意味着未来有更大的机会接上其他数字从而可能获得更长的子序列。它并没有改变当前tails的长度但优化了潜在的结构。答案遍历结束后tails的长度就是最长上升子序列的长度。本质这种方法可以理解为在动态规划dp数组的基础上额外维护了一个关于“结尾最小值”的贪心策略并利用其单调性进行二分加速。它求出的长度是正确的但tails数组本身不一定是最长上升子序列的真实序列。实操心得面试中如果被问到最长上升子序列先给出 O(n²) 的动态规划解法是稳妥的。如果面试官追问优化再引出这种 O(n log n) 的巧妙解法会大大加分。关键在于理解tails数组含义的转变——从存储“长度”变为存储“特定长度下的最小结尾”。4.2 案例二01背包问题的空间优化滚动数组回顾我们定义的二维状态dp[i][c]。观察状态转移方程dp[i][c] max(dp[i-1][c], dp[i-1][c - weight[i]] value[i])。你会发现计算第i行的数据时只依赖于第i-1行的数据。也就是说我们并不需要保存从0到i-2的所有历史数据。空间优化技巧滚动数组我们可以只用一个一维数组dp[c]来表示“容量为c时的最大价值”。在计算过程中我们从后向前遍历容量c。初始时dp[c]代表i0没有物品时的状态全部为0。当我们处理第i件物品时这个一维数组dp在逻辑上还保存着i-1件物品时的结果。对于容量c从W遍历到weight[i]必须逆序我们执行dp[c] max(dp[c], dp[c - weight[i]] value[i])dp[c]等号右边对应二维情况下不选第i件物品的方案即dp[i-1][c]。因为dp[c]还没有被本轮更新它存储的就是上一轮i-1的结果。dp[c - weight[i]] value[i]对应二维情况下选择第i件物品的方案即dp[i-1][c-weight[i]] value[i]。因为c是从大到小遍历的所以当计算dp[c]时dp[c-weight[i]]也一定是上一轮i-1的结果没有被本轮修改过。为什么必须逆序这是关键如果顺序遍历c从weight[i]到W会怎样假设weight[i]2, value[i]5。计算dp[2] max(dp[2], dp[0]5) 5。此时dp[2]被更新为5代表考虑了第i件物品。接着计算dp[4] max(dp[4], dp[2]5)。注意这里的dp[2]已经是本轮更新后的值5了这意味着dp[4] max(..., 5510)相当于第i件物品被重复计算了两次因为dp[2]已经包含了一件物品i再加5就变成了两件。这完全违背了“01背包”每件物品只能选一次的原则。 逆序遍历保证了在计算dp[c]时它所依赖的dp[c-weight[i]]是“纯净”的、未被本轮物品污染过的状态。优化结果空间复杂度从 O(N*W) 降为 O(W)。这是一个非常显著的优化尤其当物品数量N很大时。注意事项滚动数组优化是动态规划中一个非常经典的技巧但并非所有问题都适用。它适用于当前状态只依赖于上一行或前几行状态的情况。在应用时务必仔细分析依赖关系确定遍历顺序正序、逆序、甚至更复杂的顺序否则极易出错。我个人的习惯是先写出清晰的二维DP确认逻辑无误后再考虑是否可以以及如何进行空间优化。5. 动态规划的变种与常见问题模式动态规划不是一个死板的算法而是一个框架。很多问题可以通过巧妙的建模转化为动态规划问题。以下是一些常见的模式5.1 区间动态规划这类问题通常涉及对一个序列或区间进行一系列操作求最优解。状态定义往往与区间有关。典型问题矩阵连乘、石子合并、最长回文子串。状态设计通常定义dp[i][j]表示区间[i, j]上的最优解。转移方程通常需要枚举区间分割点k(i k j)将大区间[i, j]分解为两个子区间[i, k]和[k1, j]然后合并子问题的解。例如石子合并问题dp[i][j] min(dp[i][k] dp[k1][j] sum(i, j))其中sum(i,j)是合并区间[i,j]的代价。计算顺序由于计算大区间需要用到更小的区间所以通常按照区间长度从小到大进行循环。5.2 状态压缩动态规划当状态中的某些维度是布尔值或状态数很少时可以用一个整数的二进制位来表示状态从而压缩空间。典型问题旅行商问题、棋盘覆盖问题如用1*2骨牌覆盖网格。状态设计例如在旅行商问题中需要记录已经访问过哪些城市。如果有n个城市可以用一个n位的二进制数mask表示第i位为1表示城市i已访问。状态可以定义为dp[mask][i]表示从起点出发访问了mask表示的城市集合最后停留在城市i的最小花费。优势与难点极大地减少了状态表示的空间但代码可读性会下降需要熟练运用位运算如(mask i) 1检查第i位mask | (1 i)设置第i位。5.3 树形动态规划在树形结构如公司层级、决策树上进行动态规划。通常需要递归地进行后序遍历。典型问题二叉树中的最大路径和、公司派对的最大快乐值、没有上司的舞会。状态设计通常为每个节点设计一个状态数组。例如在“没有上司的舞会”中可以为每个员工节点u定义dp[u][0]员工u不参加舞会时以其为根的子树能获得的最大快乐值。dp[u][1]员工u参加舞会时以其为根的子树能获得的最大快乐值。转移方程根据父子关系构建。dp[u][0] sum( max(dp[v][0], dp[v][1]) )v是u的子节点。u不参加子节点可参加可不参加。dp[u][1] happy[u] sum( dp[v][0] )。u参加则子节点都不能参加。5.4 数位动态规划用于解决与数字的数位个、十、百...相关的计数或求值问题。典型问题统计区间[L, R]内满足某种条件如不含数字4或各位数字之和为特定值的数字个数。核心思想将数字按位拆解逐位决策。状态通常包括当前处理到第几位 (pos)、前几位是否已经小于上限 (limit)、前导零状态 (lead)、以及根据题目要求需要的其他状态如各位数字之和sum、前一位数字pre等。实现方式通常采用记忆化搜索DFS 记忆化来实现比迭代循环更直观。6. 实战调试与思维训练指南理论懂了但一写就错这是学习动态规划的正常阶段。下面分享一些调试技巧和提升思维的方法。6.1 调试技巧打印DP表与手算小规模案例动态规划的bug往往隐藏在状态定义或转移方程的细节中。最有效的调试方法就是打印出整个DP表并与你手算的小规模结果进行对比。操作步骤构造最小可复现案例不要一上来就用复杂的测试用例。用一个足够小、你大脑能完全模拟的输入。例如对于背包问题用2-3件物品容量为5。手动推导在纸上画出二维表格根据你的状态定义和转移方程一步步填满这个表格。这是检验你思路是否清晰的终极标准。程序输出在你的代码中在计算完DP表后将其完整打印出来格式化对齐更好。逐格对比将程序输出的表格与你手算的表格进行逐格对比。第一个出现差异的格子就是你的bug所在。仔细检查这个格子的计算过程它依赖的前状态对吗转移方程写对了吗边界条件数组越界考虑到了吗常见错误点检查清单数组大小dp数组的长度是否足够通常是n1或W1因为0下标常用来表示边界。初始化dp[0][...]和dp[...][0]初始化对了吗是否符合状态定义循环范围i和c的循环是从0开始还是1开始结束条件是否正确还是状态转移条件在状态转移前是否检查了前置条件如背包容量是否足够c weight[i]如果条件不满足应该怎么处理通常是直接继承dp[i-1][c]顺序问题如果使用了滚动数组优化遍历顺序尤其是内层容量循环是否正确是正序还是逆序6.2 思维训练如何培养“动态规划思维”看到新问题如何想到用动态规划这需要刻意练习。识别问题特征求最值最大值、最小值、最长、最短、最多方案数等。计数问题有多少种方式、多少种路径等。可行性问题是否存在某种方案。同时问题可以被分解为规模更小的相似子问题。尝试暴力搜索先思考最暴力的解法如递归、回溯枚举所有可能。在思考暴力解的过程中你自然会发现很多重复的计算路径。这些重复的路径就是“重叠子问题”的线索。定义“状态”问自己“在暴力搜索的过程中是什么参数在决定当前的局面” 这些参数通常就是状态的定义。例如在背包问题中是“当前考虑到第几个物品”和“剩余容量”在矩阵路径中是“当前坐标”。寻找“选择”与“转移”在当前状态下你可以做出哪些“选择”比如选或不选往左走还是往右走做出每个选择后状态会如何变化这个变化关系就是状态转移方程。从简单问题开始刷题按照专题和难度循序渐进。一个经典的路线是入门斐波那契、爬楼梯、最小路径和。基础不同路径、01背包、完全背包、最长上升子序列。进阶打家劫舍系列、股票买卖系列、子序列问题编辑距离、最长公共子序列。提高区间DP、状态压缩DP、树形DP。我个人最受用的一个习惯是每解决一道动态规划问题不仅写出代码还要用文字在注释或笔记中清晰地复述以下内容1) 状态定义2) 状态转移方程及推导理由3) 初始化4) 计算顺序5) 最终答案在哪。这个过程能极大地加深理解形成肌肉记忆。动态规划确实有门槛但一旦跨越你会发现很多复杂的优化问题都变得有迹可循。它更像是一种将问题“结构化”的思维工具而不仅仅是算法模板。多思考“为什么这样定义状态”比死记硬背十道题的代码更有价值。当你再遇到类似“最长上升子序列”或“背包”的变种时你就能从容地分析变化设计出属于自己的状态和方程了。