1. 项目概述从“子问题”视角拆解动态规划动态规划Dynamic Programming, DP是算法领域里一个既经典又让不少学习者感到“头大”的话题。很多人一听到“动态规划”脑海里立刻浮现出状态转移方程、最优子结构、重叠子问题这些术语感觉抽象又复杂。但如果你曾为“最长上升子序列”或“01背包问题”绞尽脑汁然后某天突然灵光一现理解了其核心不过是“把大问题拆成小问题并记住小问题的答案”那么恭喜你你已经摸到了动态规划的门道。今天我们不谈那些高深的理论就从一个最核心、最实战的角度切入——子问题分析。这是动态规划从“看懂答案”到“自己设计”的关键一跃。所谓“子问题分析”就是面对一个复杂问题时我们如何定义出那些规模更小、结构相同、且能被重复利用的“小问题”。这听起来简单做起来却需要清晰的思路和一定的模式识别能力。我们常常在LeetCode上看到一道DP题看了题解后恍然大悟“哦原来dp[i]表示的是这个意思”但下次遇到新题又不知从何下手。问题的根源往往在于我们记住了“状态定义”这个结果却忽略了得出这个定义的“分析过程”。本文将聚焦于Level 2的难度通过几个典型案例深入剖析“子问题”是如何被识别、定义和串联起来的让你获得一种可迁移的分析能力而不仅仅是背诵几个模板。2. 动态规划的核心最优子结构与重叠子问题再认识在深入案例之前我们有必要重新审视动态规划赖以成立的两大基石最优子结构和重叠子问题。很多教程会告诉你这是DP的条件但今天我们换个角度看看它们如何直接指导我们进行子问题分析。2.1 最优子结构决策的“连锁反应”最优子结构意味着一个问题的最优解包含了其子问题的最优解。这听起来像句绕口令我们用一个生活化的例子来理解假设你要从北京开车到上海并且想找到最短路径。如果这条最短路径经过了南京那么从北京到南京的这段子路径也一定是北京到南京所有可能路径中的最短路径。不可能存在一条整体最短的路径其中某一段却不是最短的。这就是最优子结构。在算法问题中最优子结构为我们分析子问题提供了方向性指引。它告诉我们在思考大问题P时我们可以假设所有更小规模的同类问题P都已经得到了最优解。我们的任务就变成了如何利用这些已知的、最优的子问题解通过某种决策构造出大问题P的最优解。这个“决策”点就是状态转移的契机。例如在背包问题中“是否将当前物品装入背包”就是一个决策在子序列问题中“当前字符是否纳入考虑范围”也是一个决策。识别出这个关键的决策步骤是定义子问题的起点。注意不是所有具有子结构的问题都能用动态规划。最优子结构要求子问题间必须独立。如果一个子问题的解依赖于另一个子问题的具体选择而不仅仅是最优值那么这个问题可能更适合用回溯或搜索来解决。2.2 重叠子问题记忆化的价值所在重叠子问题是指在递归求解的过程中相同的子问题会被多次计算。斐波那契数列就是最经典的例子计算F(5)需要计算F(4)和F(3)计算F(4)又需要计算F(3)和F(2)这里F(3)就被重复计算了。重叠子现象的存在正是我们使用动态规划或者说“记忆化搜索”来提升效率的根本原因。它从另一个侧面帮助我们定义子问题我们定义出的子问题必须是在求解大问题过程中会被反复用到的。如果你定义了一个子问题但在整个求解过程中只被计算一次那么为它设计状态和转移可能就是多余的简单的递归或分治或许就够了。在进行子问题分析时我们可以通过思考一个朴素的递归解法来验证重叠子问题。试着在脑海里画一棵递归树如果发现很多树枝长得一模一样即参数相同的函数调用频繁出现那么动态规划的机会就来了。此时我们定义子问题的目标就是用一个数组DP表来唯一标识递归树中每一个不同的节点即每一组不同的参数从而避免重复计算。3. 子问题分析实战案例一最长递增子序列LIS最长递增子序列Longest Increasing Subsequence, LIS是动态规划的入门必修课也是一个绝佳的子问题分析案例。题目很简单给定一个整数数组nums找到其中最长的、严格递增的子序列的长度。3.1 第一步寻找问题切分点与决策面对整个数组我们如何逐步缩小问题规模一个自然的想法是关注数组的前缀。即先解决“只考虑数组前i个元素”时的LIS长度。但这够吗我们定义dp[i]为以第i个数字结尾的最长递增子序列的长度。为什么是“以...结尾”这是本题子问题分析的精髓。让我们思考决策点。对于一个递增子序列其最后一个元素至关重要因为它决定了后续哪些元素可以被添加进来。如果我们定义dp[i]仅仅是“前i个元素中的LIS长度”那么当我们要计算dp[i1]时我们并不知道之前找到的那个最长的子序列的最后一个元素是谁、是多少。这导致我们无法判断nums[i1]能否接在这个子序列后面形成更长的序列。信息不足状态转移就无法进行。因此我们必须让子问题携带更关键的信息。定义dp[i]为“以nums[i]结尾的LIS长度”这个状态包含了我们做决策所需的全部信息序列的结尾元素就是nums[i]。现在要计算dp[i]我们需要考虑在i之前的所有位置j0 j i。决策就是是否可以将nums[i]接在以nums[j]结尾的子序列后面如果可以即nums[i] nums[j]那么就有可能形成一个更长的、以nums[i]结尾的子序列其长度为dp[j] 1。3.2 第二步状态定义与转移方程推导基于以上分析我们形式化地定义状态状态定义dp[i]表示以nums[i]这个元素结尾的、最长递增子序列的长度。初始状态对于任意位置i最起码它自身可以构成一个长度为1的子序列。因此所有dp[i]初始值均为1。状态转移方程对于每一个i遍历所有j i。如果nums[i] nums[j]说明nums[i]可以接在nums[j]后面。此时以nums[i]结尾的LIS长度至少可以是dp[j] 1。我们要在所有可行的j中选择一个能使dp[i]最大的。因此转移方程为dp[i] max(dp[i], dp[j] 1) for all j i where nums[i] nums[j]最终答案数组dp中的最大值因为整个数组的LIS不一定以最后一个元素结尾。3.3 第三步复杂度分析与实操要点时间复杂度为O(n²)因为对于每个i我们都需要遍历它之前的所有j。空间复杂度为O(n)。实操心得与常见陷阱初始化的重要性务必记得将每个dp[i]初始化为1。我曾见过有人初始化为0导致结果永远比正确答案少1。最终答案不是dp[n-1]这是新手常犯的错误。LIS可能出现在数组的任何一个位置结尾所以最终答案必须是max(dp)。“严格递增”的判断转移条件nums[i] nums[j]是严格大于。如果题目要求“非严格递增”即允许相等则条件应改为nums[i] nums[j]。进阶优化O(n²)的解法在面试中通常足够但存在一种利用“耐心排序”思想将时间复杂度优化至O(n log n)的贪心二分查找方法。其核心是维护一个“最小尾部元素数组”但理解难度较高。在Level2阶段掌握基础的DP解法并清晰理解其子问题定义更为关键。4. 子问题分析实战案例二零钱兑换完全背包问题零钱兑换问题给你一个整数数组coins表示不同面额的硬币每种硬币的数量无限这是一个关键点即“完全背包”问题以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果无法凑出则返回-1。4.1 第一步识别问题类型与决策维度这个问题有明显的“目标值”总金额amount和“可选择的物品”硬币面额。每个硬币可以被无限次选取这指向了“完全背包”模型。在背包问题中子问题的规模通常由两个维度来缩减可选择的物品范围和背包的容量。对于完全背包一个经典的子问题定义是dp[i][j]表示只使用前i种硬币coins[0...i-1]凑出总金额j所需的最少硬币数量。这里就包含了两个缩小的维度硬币种类i和金额j。然而在零钱兑换问题中我们还可以进一步优化状态定义。因为硬币无限且我们通常更关心最终凑出的金额一个更简洁、更常用的定义是dp[j]表示凑出总金额j所需的最少硬币个数。这里子问题只通过目标金额j来划分。为什么可以这样因为硬币无限当我们考虑金额j时我们可以选择任何面额的硬币而不需要记录已经使用了前几种硬币。这体现了“完全背包”问题可以优化为一维DP的特点。4.2 第二步一维状态定义与转移逻辑我们采用一维DP数组dp长度为amount 1。状态定义dp[j]表示凑出总金额j所需的最少硬币数量。初始状态dp[0] 0凑出金额0需要0个硬币。这是一个非常重要的“基底”。其他dp[j]初始化为一个很大的数如amount 1或float(inf)代表暂时无法凑出。状态转移方程对于每一个目标金额j从1遍历到amount我们遍历每一种硬币面额coin。如果j coin即当前金额至少能放下这枚硬币那么我们可以考虑使用这枚硬币。使用这枚硬币后剩余金额是j - coin凑出剩余金额的最少硬币数是dp[j - coin]。因此一种可能的方案是dp[j - coin] 1加上当前这枚硬币。我们要在所有可行的硬币选择中取最小值。所以转移方程为dp[j] min(dp[j], dp[j - coin] 1) for coin in coins if j coin最终答案如果dp[amount]仍然是我们初始设置的那个很大的数说明无法凑出返回-1否则返回dp[amount]。4.3 第三步遍历顺序的奥秘与问题排查为什么遍历顺序是“先遍历金额j正序再遍历硬币coin”这与“完全背包”的内涵有关。正序遍历金额j意味着在计算dp[j]时dp[j - coin]可能已经在本轮遍历中更新过了因为j - coin j。dp[j - coin]如果被更新它代表的是“已经考虑过使用当前种类的硬币coin”的情况下凑出金额j-coin的最优解。这就允许了同一枚硬币被多次使用符合“完全”的要求。如果先遍历硬币再遍历金额得到的是“排列数”相关的解法不适合本题求最小个数的场景。常见问题排查初始化陷阱dp[0] 0是正确计算的起点。如果错误地初始化为inf整个DP数组将无法更新。无法凑出的判断初始值要设得比可能的最大答案大。通常设为amount 1是安全的因为即使全用1元硬币最多也只需要amount个。转移方程中的1这个1代表当前选择的这枚硬币。忘记加1是常见错误会导致结果少算硬币数量。测试用例用coins [2], amount 3测试。正确的dp过程应该是dp[1]inf,dp[2]1,dp[3]inf因为3-21dp[1]inf所以dp[3]无法更新最终返回-1。这个用例能很好地检验边界逻辑。5. 子问题分析实战案例三编辑距离字符串DP编辑距离Levenshtein distance是字符串动态规划的标杆问题给定两个单词word1和word2计算将word1转换成word2所使用的最少操作数。操作包括插入一个字符、删除一个字符、替换一个字符。5.1 第一步构建二维状态空间两个字符串的动态规划通常需要二维的DP表来刻画子问题。因为我们需要同时追踪两个字符串的匹配进度。状态定义dp[i][j]表示将word1的前i个字符即word1[0...i-1]转换成word2的前j个字符即word2[0...j-1]所需的最少操作次数。这里使用i和j表示长度而不是下标可以简化边界条件空字符串的处理。这个定义完美体现了子问题的划分我们将原始的大问题转换整个word1到整个word2分解为一系列更小的问题转换word1的某个前缀到word2的某个前缀。5.2 第二步基于“最后一步操作”推导转移方程动态规划转移方程的核心思想往往是考虑达到当前状态(i, j)的最后一步可能是什么操作。对于dp[i][j]我们有三种可能的“最后一步”删除如果word1的前i个字符已经能转换成word2的前j-1个字符那么我只需要在word1末尾插入word2的第j个字符即可。对应操作数dp[i][j-1] 1一次插入。插入如果word1的前i-1个字符已经能转换成word2的前j个字符那么我只需要删除word1的第i个字符即可。对应操作数dp[i-1][j] 1一次删除。替换或不操作如果word1的前i-1个字符已经能转换成word2的前j-1个字符那么如果word1[i-1]等于word2[j-1]注意下标转换我们不需要任何操作直接继承dp[i-1][j-1]。如果不相等我们需要将word1[i-1]替换为word2[j-1]操作数为dp[i-1][j-1] 1。我们要的是最少操作数所以dp[i][j]应该取上述三种可能的最小值。 因此状态转移方程为if word1[i-1] word2[j-1]: dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1]) else: dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1] 1)5.3 第三步初始化与填表顺序初始化dp[0][j]表示将空字符串转换为word2的前j个字符显然需要j次插入操作。dp[i][0]表示将word1的前i个字符转换为空字符串显然需要i次删除操作。 所以dp[0][j] jdp[i][0] i填表顺序由于dp[i][j]依赖于其左方(dp[i][j-1])、上方(dp[i-1][j])和左上方(dp[i-1][j-1])的值因此我们可以按行i从1到len(word1)或按列j从1到len(word2)顺序填充只要保证在计算dp[i][j]时它依赖的三个值都已经计算出来即可。通常采用逐行遍历。实操中的调试技巧手动画表对于word1”horse”, word2”ros”这样的小例子在纸上画出DP表手动填充几行是理解整个过程最有效的方法。你会清晰地看到每个格子是如何从它的“邻居”计算出来的。理解“等价操作”有时删除word1的一个字符等价于向word2插入一个字符。从状态转移的对称性上可以理解dp[i-1][j] 1和dp[i][j-1] 1在数学形式上是等价的但在语义上一个是删除一个是插入。空间优化类似于背包问题编辑距离的DP也可以优化到一维数组只保留一行或一列因为每一行只依赖于上一行。但在面试或初学时先写出清晰的二维DP版本更重要。6. 子问题分析的通用模式与思维框架通过以上三个案例我们可以提炼出一些分析子问题的通用模式和思维框架。6.1 常见的子问题定义范式线性序列问题如LIS、最大子数组和范式dp[i]表示以第i个元素为结尾的某种最优解。关键点状态必须包含“结尾”信息以保证在状态转移时新加入的元素能与已知的“结尾”产生关系从而做出决策。思考当问题与序列的顺序有关且新状态与序列末尾状态强相关时优先考虑此范式。背包问题如零钱兑换、分割等和子集范式dp[i][j]表示考虑前i件物品在容量/目标为j的限制下的最优解。优化后常为dp[j]。关键点子问题由两个维度界定物品的范围和容量的限制。完全背包/01背包的区别体现在遍历顺序上。思考当问题涉及“选择”一组物品以达到某个目标总价值最大、总重量最小、刚好装满且目标有一个明确的量化限制时考虑背包模型。双序列问题如编辑距离、最长公共子序列LCS范式dp[i][j]表示针对第一个序列的前i个元素和第二个序列的前j个元素的某种最优解。关键点状态同时追踪两个序列的进度。转移方程通常考虑两个序列末尾元素的匹配情况相等、不相等。思考当问题涉及两个字符串或序列的比对、匹配、转换时二维DP是标准思路。区间问题如矩阵连乘、石子合并范式dp[i][j]表示针对序列/区间[i...j]的最优解。关键点状态表示一个区间转移时通常枚举区间内的一个分割点k将大区间[i, j]分解为两个子区间[i, k]和[k1, j]。思考当问题的操作对象是序列的一个连续片段且最优解可能依赖于如何划分这个片段时考虑区间DP。6.2 四步分析法从问题到DP方程当你拿到一个新问题时可以尝试以下四个步骤来拆解步骤一定义状态子问题。问自己用什么参数可以唯一标识一个子问题通常参数代表问题的规模如序列长度、物品个数、目标金额。状态定义要包含做出下一步决策所需的关键信息如LIS中的“结尾元素”。步骤二确定状态转移方程。这是最核心的一步。思考如何通过更小的子问题已知最优解来构造出当前子问题的最优解通常的思考模式是“要达到当前状态最后一步可能做了什么操作”如编辑距离或者“在当前状态下我可以做出什么选择”如背包问题。用数学公式表达这种关系。步骤三确定初始状态边界条件。最小的、不可再分的子问题是什么它们的解通常是显而易见的如空序列、目标为0、区间长度为1。正确初始化是DP正确运行的起点。步骤四确定计算顺序填表顺序。要计算dp[x]需要先知道哪些其他的dp[y]确保这些dp[y]在dp[x]之前被计算出来。这通常决定了我们的循环嵌套顺序。6.3 避坑指南与经验之谈状态定义过于笼统如果发现定义的状态无法写出转移方程很可能是因为状态携带的信息不足。回顾LIS的例子从“前i个”调整为“以i结尾”就是关键一步。试着给状态增加一个维度如一个布尔值、一个结尾信息。忽视重叠子问题如果你能写出一个清晰的递归函数但递归树中有大量重复节点这就是DP的强烈信号。用记忆化搜索自顶向下缓存往往是实现DP最直观的方式尤其适合状态转移关系复杂但子问题定义清晰的情况。初始化和边界处理错误这是DP调试中最常见的错误。务必仔细考虑dp[0]、dp[0][0]、dp[i][0]、dp[0][j]这些边界情况。多设置几个简单的测试用例如空输入、单个元素输入来验证。遍历顺序错误特别是在背包问题中一维DP下“先遍历物品还是先遍历容量”、“容量是正序还是逆序”直接决定了是01背包还是完全背包。如果不确定回归到二维DP的定义去理解或者画一个小的DP表模拟一下过程。追求一维优化过早在理解不深的时候优先写出直观的二维甚至三维DP。正确性永远比空间优化更重要。在确保二维DP正确无误后再考虑是否可以优化状态维度。一维DP是优化后的结果而不是思考的起点。动态规划的子问题分析本质上是一种“化整为零、从底向上”的系统性思考方式。它要求我们放弃一眼看到全局答案的幻想而是耐心地定义出所有可能的小问题并找出它们之间严谨的递推关系。这种能力需要通过大量练习来培养。从经典的模型LIS、背包、LCS、编辑距离入手深刻理解每一个案例中“状态定义”的由来和“转移方程”的推导过程比刷很多道题但一知半解要有效得多。当你再遇到新的DP问题时试着问自己“这个问题最自然的子问题划分是什么”“要达到这个状态它的最后一步可能是什么”多进行这样的思维训练你会发现自己拆解复杂问题的能力在不知不觉中得到了质的提升。 动态规划子问题分析实战：从LIS、零钱兑换到编辑距离
1. 项目概述从“子问题”视角拆解动态规划动态规划Dynamic Programming, DP是算法领域里一个既经典又让不少学习者感到“头大”的话题。很多人一听到“动态规划”脑海里立刻浮现出状态转移方程、最优子结构、重叠子问题这些术语感觉抽象又复杂。但如果你曾为“最长上升子序列”或“01背包问题”绞尽脑汁然后某天突然灵光一现理解了其核心不过是“把大问题拆成小问题并记住小问题的答案”那么恭喜你你已经摸到了动态规划的门道。今天我们不谈那些高深的理论就从一个最核心、最实战的角度切入——子问题分析。这是动态规划从“看懂答案”到“自己设计”的关键一跃。所谓“子问题分析”就是面对一个复杂问题时我们如何定义出那些规模更小、结构相同、且能被重复利用的“小问题”。这听起来简单做起来却需要清晰的思路和一定的模式识别能力。我们常常在LeetCode上看到一道DP题看了题解后恍然大悟“哦原来dp[i]表示的是这个意思”但下次遇到新题又不知从何下手。问题的根源往往在于我们记住了“状态定义”这个结果却忽略了得出这个定义的“分析过程”。本文将聚焦于Level 2的难度通过几个典型案例深入剖析“子问题”是如何被识别、定义和串联起来的让你获得一种可迁移的分析能力而不仅仅是背诵几个模板。2. 动态规划的核心最优子结构与重叠子问题再认识在深入案例之前我们有必要重新审视动态规划赖以成立的两大基石最优子结构和重叠子问题。很多教程会告诉你这是DP的条件但今天我们换个角度看看它们如何直接指导我们进行子问题分析。2.1 最优子结构决策的“连锁反应”最优子结构意味着一个问题的最优解包含了其子问题的最优解。这听起来像句绕口令我们用一个生活化的例子来理解假设你要从北京开车到上海并且想找到最短路径。如果这条最短路径经过了南京那么从北京到南京的这段子路径也一定是北京到南京所有可能路径中的最短路径。不可能存在一条整体最短的路径其中某一段却不是最短的。这就是最优子结构。在算法问题中最优子结构为我们分析子问题提供了方向性指引。它告诉我们在思考大问题P时我们可以假设所有更小规模的同类问题P都已经得到了最优解。我们的任务就变成了如何利用这些已知的、最优的子问题解通过某种决策构造出大问题P的最优解。这个“决策”点就是状态转移的契机。例如在背包问题中“是否将当前物品装入背包”就是一个决策在子序列问题中“当前字符是否纳入考虑范围”也是一个决策。识别出这个关键的决策步骤是定义子问题的起点。注意不是所有具有子结构的问题都能用动态规划。最优子结构要求子问题间必须独立。如果一个子问题的解依赖于另一个子问题的具体选择而不仅仅是最优值那么这个问题可能更适合用回溯或搜索来解决。2.2 重叠子问题记忆化的价值所在重叠子问题是指在递归求解的过程中相同的子问题会被多次计算。斐波那契数列就是最经典的例子计算F(5)需要计算F(4)和F(3)计算F(4)又需要计算F(3)和F(2)这里F(3)就被重复计算了。重叠子现象的存在正是我们使用动态规划或者说“记忆化搜索”来提升效率的根本原因。它从另一个侧面帮助我们定义子问题我们定义出的子问题必须是在求解大问题过程中会被反复用到的。如果你定义了一个子问题但在整个求解过程中只被计算一次那么为它设计状态和转移可能就是多余的简单的递归或分治或许就够了。在进行子问题分析时我们可以通过思考一个朴素的递归解法来验证重叠子问题。试着在脑海里画一棵递归树如果发现很多树枝长得一模一样即参数相同的函数调用频繁出现那么动态规划的机会就来了。此时我们定义子问题的目标就是用一个数组DP表来唯一标识递归树中每一个不同的节点即每一组不同的参数从而避免重复计算。3. 子问题分析实战案例一最长递增子序列LIS最长递增子序列Longest Increasing Subsequence, LIS是动态规划的入门必修课也是一个绝佳的子问题分析案例。题目很简单给定一个整数数组nums找到其中最长的、严格递增的子序列的长度。3.1 第一步寻找问题切分点与决策面对整个数组我们如何逐步缩小问题规模一个自然的想法是关注数组的前缀。即先解决“只考虑数组前i个元素”时的LIS长度。但这够吗我们定义dp[i]为以第i个数字结尾的最长递增子序列的长度。为什么是“以...结尾”这是本题子问题分析的精髓。让我们思考决策点。对于一个递增子序列其最后一个元素至关重要因为它决定了后续哪些元素可以被添加进来。如果我们定义dp[i]仅仅是“前i个元素中的LIS长度”那么当我们要计算dp[i1]时我们并不知道之前找到的那个最长的子序列的最后一个元素是谁、是多少。这导致我们无法判断nums[i1]能否接在这个子序列后面形成更长的序列。信息不足状态转移就无法进行。因此我们必须让子问题携带更关键的信息。定义dp[i]为“以nums[i]结尾的LIS长度”这个状态包含了我们做决策所需的全部信息序列的结尾元素就是nums[i]。现在要计算dp[i]我们需要考虑在i之前的所有位置j0 j i。决策就是是否可以将nums[i]接在以nums[j]结尾的子序列后面如果可以即nums[i] nums[j]那么就有可能形成一个更长的、以nums[i]结尾的子序列其长度为dp[j] 1。3.2 第二步状态定义与转移方程推导基于以上分析我们形式化地定义状态状态定义dp[i]表示以nums[i]这个元素结尾的、最长递增子序列的长度。初始状态对于任意位置i最起码它自身可以构成一个长度为1的子序列。因此所有dp[i]初始值均为1。状态转移方程对于每一个i遍历所有j i。如果nums[i] nums[j]说明nums[i]可以接在nums[j]后面。此时以nums[i]结尾的LIS长度至少可以是dp[j] 1。我们要在所有可行的j中选择一个能使dp[i]最大的。因此转移方程为dp[i] max(dp[i], dp[j] 1) for all j i where nums[i] nums[j]最终答案数组dp中的最大值因为整个数组的LIS不一定以最后一个元素结尾。3.3 第三步复杂度分析与实操要点时间复杂度为O(n²)因为对于每个i我们都需要遍历它之前的所有j。空间复杂度为O(n)。实操心得与常见陷阱初始化的重要性务必记得将每个dp[i]初始化为1。我曾见过有人初始化为0导致结果永远比正确答案少1。最终答案不是dp[n-1]这是新手常犯的错误。LIS可能出现在数组的任何一个位置结尾所以最终答案必须是max(dp)。“严格递增”的判断转移条件nums[i] nums[j]是严格大于。如果题目要求“非严格递增”即允许相等则条件应改为nums[i] nums[j]。进阶优化O(n²)的解法在面试中通常足够但存在一种利用“耐心排序”思想将时间复杂度优化至O(n log n)的贪心二分查找方法。其核心是维护一个“最小尾部元素数组”但理解难度较高。在Level2阶段掌握基础的DP解法并清晰理解其子问题定义更为关键。4. 子问题分析实战案例二零钱兑换完全背包问题零钱兑换问题给你一个整数数组coins表示不同面额的硬币每种硬币的数量无限这是一个关键点即“完全背包”问题以及一个整数amount表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果无法凑出则返回-1。4.1 第一步识别问题类型与决策维度这个问题有明显的“目标值”总金额amount和“可选择的物品”硬币面额。每个硬币可以被无限次选取这指向了“完全背包”模型。在背包问题中子问题的规模通常由两个维度来缩减可选择的物品范围和背包的容量。对于完全背包一个经典的子问题定义是dp[i][j]表示只使用前i种硬币coins[0...i-1]凑出总金额j所需的最少硬币数量。这里就包含了两个缩小的维度硬币种类i和金额j。然而在零钱兑换问题中我们还可以进一步优化状态定义。因为硬币无限且我们通常更关心最终凑出的金额一个更简洁、更常用的定义是dp[j]表示凑出总金额j所需的最少硬币个数。这里子问题只通过目标金额j来划分。为什么可以这样因为硬币无限当我们考虑金额j时我们可以选择任何面额的硬币而不需要记录已经使用了前几种硬币。这体现了“完全背包”问题可以优化为一维DP的特点。4.2 第二步一维状态定义与转移逻辑我们采用一维DP数组dp长度为amount 1。状态定义dp[j]表示凑出总金额j所需的最少硬币数量。初始状态dp[0] 0凑出金额0需要0个硬币。这是一个非常重要的“基底”。其他dp[j]初始化为一个很大的数如amount 1或float(inf)代表暂时无法凑出。状态转移方程对于每一个目标金额j从1遍历到amount我们遍历每一种硬币面额coin。如果j coin即当前金额至少能放下这枚硬币那么我们可以考虑使用这枚硬币。使用这枚硬币后剩余金额是j - coin凑出剩余金额的最少硬币数是dp[j - coin]。因此一种可能的方案是dp[j - coin] 1加上当前这枚硬币。我们要在所有可行的硬币选择中取最小值。所以转移方程为dp[j] min(dp[j], dp[j - coin] 1) for coin in coins if j coin最终答案如果dp[amount]仍然是我们初始设置的那个很大的数说明无法凑出返回-1否则返回dp[amount]。4.3 第三步遍历顺序的奥秘与问题排查为什么遍历顺序是“先遍历金额j正序再遍历硬币coin”这与“完全背包”的内涵有关。正序遍历金额j意味着在计算dp[j]时dp[j - coin]可能已经在本轮遍历中更新过了因为j - coin j。dp[j - coin]如果被更新它代表的是“已经考虑过使用当前种类的硬币coin”的情况下凑出金额j-coin的最优解。这就允许了同一枚硬币被多次使用符合“完全”的要求。如果先遍历硬币再遍历金额得到的是“排列数”相关的解法不适合本题求最小个数的场景。常见问题排查初始化陷阱dp[0] 0是正确计算的起点。如果错误地初始化为inf整个DP数组将无法更新。无法凑出的判断初始值要设得比可能的最大答案大。通常设为amount 1是安全的因为即使全用1元硬币最多也只需要amount个。转移方程中的1这个1代表当前选择的这枚硬币。忘记加1是常见错误会导致结果少算硬币数量。测试用例用coins [2], amount 3测试。正确的dp过程应该是dp[1]inf,dp[2]1,dp[3]inf因为3-21dp[1]inf所以dp[3]无法更新最终返回-1。这个用例能很好地检验边界逻辑。5. 子问题分析实战案例三编辑距离字符串DP编辑距离Levenshtein distance是字符串动态规划的标杆问题给定两个单词word1和word2计算将word1转换成word2所使用的最少操作数。操作包括插入一个字符、删除一个字符、替换一个字符。5.1 第一步构建二维状态空间两个字符串的动态规划通常需要二维的DP表来刻画子问题。因为我们需要同时追踪两个字符串的匹配进度。状态定义dp[i][j]表示将word1的前i个字符即word1[0...i-1]转换成word2的前j个字符即word2[0...j-1]所需的最少操作次数。这里使用i和j表示长度而不是下标可以简化边界条件空字符串的处理。这个定义完美体现了子问题的划分我们将原始的大问题转换整个word1到整个word2分解为一系列更小的问题转换word1的某个前缀到word2的某个前缀。5.2 第二步基于“最后一步操作”推导转移方程动态规划转移方程的核心思想往往是考虑达到当前状态(i, j)的最后一步可能是什么操作。对于dp[i][j]我们有三种可能的“最后一步”删除如果word1的前i个字符已经能转换成word2的前j-1个字符那么我只需要在word1末尾插入word2的第j个字符即可。对应操作数dp[i][j-1] 1一次插入。插入如果word1的前i-1个字符已经能转换成word2的前j个字符那么我只需要删除word1的第i个字符即可。对应操作数dp[i-1][j] 1一次删除。替换或不操作如果word1的前i-1个字符已经能转换成word2的前j-1个字符那么如果word1[i-1]等于word2[j-1]注意下标转换我们不需要任何操作直接继承dp[i-1][j-1]。如果不相等我们需要将word1[i-1]替换为word2[j-1]操作数为dp[i-1][j-1] 1。我们要的是最少操作数所以dp[i][j]应该取上述三种可能的最小值。 因此状态转移方程为if word1[i-1] word2[j-1]: dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1]) else: dp[i][j] min(dp[i-1][j] 1, dp[i][j-1] 1, dp[i-1][j-1] 1)5.3 第三步初始化与填表顺序初始化dp[0][j]表示将空字符串转换为word2的前j个字符显然需要j次插入操作。dp[i][0]表示将word1的前i个字符转换为空字符串显然需要i次删除操作。 所以dp[0][j] jdp[i][0] i填表顺序由于dp[i][j]依赖于其左方(dp[i][j-1])、上方(dp[i-1][j])和左上方(dp[i-1][j-1])的值因此我们可以按行i从1到len(word1)或按列j从1到len(word2)顺序填充只要保证在计算dp[i][j]时它依赖的三个值都已经计算出来即可。通常采用逐行遍历。实操中的调试技巧手动画表对于word1”horse”, word2”ros”这样的小例子在纸上画出DP表手动填充几行是理解整个过程最有效的方法。你会清晰地看到每个格子是如何从它的“邻居”计算出来的。理解“等价操作”有时删除word1的一个字符等价于向word2插入一个字符。从状态转移的对称性上可以理解dp[i-1][j] 1和dp[i][j-1] 1在数学形式上是等价的但在语义上一个是删除一个是插入。空间优化类似于背包问题编辑距离的DP也可以优化到一维数组只保留一行或一列因为每一行只依赖于上一行。但在面试或初学时先写出清晰的二维DP版本更重要。6. 子问题分析的通用模式与思维框架通过以上三个案例我们可以提炼出一些分析子问题的通用模式和思维框架。6.1 常见的子问题定义范式线性序列问题如LIS、最大子数组和范式dp[i]表示以第i个元素为结尾的某种最优解。关键点状态必须包含“结尾”信息以保证在状态转移时新加入的元素能与已知的“结尾”产生关系从而做出决策。思考当问题与序列的顺序有关且新状态与序列末尾状态强相关时优先考虑此范式。背包问题如零钱兑换、分割等和子集范式dp[i][j]表示考虑前i件物品在容量/目标为j的限制下的最优解。优化后常为dp[j]。关键点子问题由两个维度界定物品的范围和容量的限制。完全背包/01背包的区别体现在遍历顺序上。思考当问题涉及“选择”一组物品以达到某个目标总价值最大、总重量最小、刚好装满且目标有一个明确的量化限制时考虑背包模型。双序列问题如编辑距离、最长公共子序列LCS范式dp[i][j]表示针对第一个序列的前i个元素和第二个序列的前j个元素的某种最优解。关键点状态同时追踪两个序列的进度。转移方程通常考虑两个序列末尾元素的匹配情况相等、不相等。思考当问题涉及两个字符串或序列的比对、匹配、转换时二维DP是标准思路。区间问题如矩阵连乘、石子合并范式dp[i][j]表示针对序列/区间[i...j]的最优解。关键点状态表示一个区间转移时通常枚举区间内的一个分割点k将大区间[i, j]分解为两个子区间[i, k]和[k1, j]。思考当问题的操作对象是序列的一个连续片段且最优解可能依赖于如何划分这个片段时考虑区间DP。6.2 四步分析法从问题到DP方程当你拿到一个新问题时可以尝试以下四个步骤来拆解步骤一定义状态子问题。问自己用什么参数可以唯一标识一个子问题通常参数代表问题的规模如序列长度、物品个数、目标金额。状态定义要包含做出下一步决策所需的关键信息如LIS中的“结尾元素”。步骤二确定状态转移方程。这是最核心的一步。思考如何通过更小的子问题已知最优解来构造出当前子问题的最优解通常的思考模式是“要达到当前状态最后一步可能做了什么操作”如编辑距离或者“在当前状态下我可以做出什么选择”如背包问题。用数学公式表达这种关系。步骤三确定初始状态边界条件。最小的、不可再分的子问题是什么它们的解通常是显而易见的如空序列、目标为0、区间长度为1。正确初始化是DP正确运行的起点。步骤四确定计算顺序填表顺序。要计算dp[x]需要先知道哪些其他的dp[y]确保这些dp[y]在dp[x]之前被计算出来。这通常决定了我们的循环嵌套顺序。6.3 避坑指南与经验之谈状态定义过于笼统如果发现定义的状态无法写出转移方程很可能是因为状态携带的信息不足。回顾LIS的例子从“前i个”调整为“以i结尾”就是关键一步。试着给状态增加一个维度如一个布尔值、一个结尾信息。忽视重叠子问题如果你能写出一个清晰的递归函数但递归树中有大量重复节点这就是DP的强烈信号。用记忆化搜索自顶向下缓存往往是实现DP最直观的方式尤其适合状态转移关系复杂但子问题定义清晰的情况。初始化和边界处理错误这是DP调试中最常见的错误。务必仔细考虑dp[0]、dp[0][0]、dp[i][0]、dp[0][j]这些边界情况。多设置几个简单的测试用例如空输入、单个元素输入来验证。遍历顺序错误特别是在背包问题中一维DP下“先遍历物品还是先遍历容量”、“容量是正序还是逆序”直接决定了是01背包还是完全背包。如果不确定回归到二维DP的定义去理解或者画一个小的DP表模拟一下过程。追求一维优化过早在理解不深的时候优先写出直观的二维甚至三维DP。正确性永远比空间优化更重要。在确保二维DP正确无误后再考虑是否可以优化状态维度。一维DP是优化后的结果而不是思考的起点。动态规划的子问题分析本质上是一种“化整为零、从底向上”的系统性思考方式。它要求我们放弃一眼看到全局答案的幻想而是耐心地定义出所有可能的小问题并找出它们之间严谨的递推关系。这种能力需要通过大量练习来培养。从经典的模型LIS、背包、LCS、编辑距离入手深刻理解每一个案例中“状态定义”的由来和“转移方程”的推导过程比刷很多道题但一知半解要有效得多。当你再遇到新的DP问题时试着问自己“这个问题最自然的子问题划分是什么”“要达到这个状态它的最后一步可能是什么”多进行这样的思维训练你会发现自己拆解复杂问题的能力在不知不觉中得到了质的提升。