1. 动态规划基础与代码随想录Day33概览动态规划作为算法领域的核心思想在解决最优化问题时展现出独特优势。代码随想录Day33这一章节聚焦动态规划的第二部分主要涵盖背包问题及其变种的解题思路。我初次接触这部分内容时曾被各种背包变体搞得晕头转向直到理清了它们之间的递推关系才豁然开朗。背包问题本质上是资源分配问题的一个经典模型。想象你有一个容量有限的背包和若干具有不同重量与价值的物品需要决定装入哪些物品才能使总价值最大化。这个看似简单的问题背后却蕴含着动态规划最精髓的状态转移思想。在代码随想录的课程体系中Day33通常安排在动态规划基础概念讲解之后作为进阶内容出现。它承接着前面斐波那契数列、爬楼梯等入门例题开始向更复杂的实际问题过渡。这个阶段的学习重点从理解递归公式转向掌握如何构建完整的状态转移方程。关键提示动态规划解题的核心在于明确dp数组定义和状态转移逻辑。很多初学者容易直接跳入代码实现反而忽略了这最重要的思考过程。2. 背包问题核心框架解析2.1 01背包问题标准解法01背包是动态规划中最经典的入门问题其特点是每种物品只能选择放入1或不放入0背包一次。我仍记得第一次写出完整解法时的兴奋感——那种将抽象思维转化为具体代码的成就感令人难忘。定义dp数组时我们通常使用二维表示法dp[i][j]表示从前i件物品中选择放入容量为j的背包所能获得的最大价值。状态转移方程则体现着动态规划的精髓dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])这个方程的含义非常直观对于第i件物品我们有两种选择——不放入背包保持前i-1件物品的最优解或者放入背包则需要在前i-1件物品中寻找剩余容量j-weight[i]时的最优解再加上当前物品的价值。在实际编码中为了优化空间复杂度我们通常会使用一维数组进行状态压缩def knapsack_01(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]注意事项内层循环必须逆序遍历这是为了避免同一物品被多次计入。这是01背包问题最易错的细节之一我在初学时曾因此debug了整整一个下午。2.2 完全背包问题变体与01背包不同完全背包允许物品被无限次选取。这个变化看似微小却完全改变了状态转移的逻辑。我第一次尝试修改01背包代码来解决完全背包时发现结果总是出错后来才明白需要调整遍历顺序。完全背包的状态转移方程与01背包类似但因为物品可以重复选取所以不需要考虑i-1的状态dp[j] max(dp[j], dp[j - weight[i]] value[i])对应的Python实现只需要将内层循环改为正序即可def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(weights[i], capacity 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]这个例子很好地展示了动态规划中定义决定实现的特点。同样的状态转移逻辑因为问题定义的微小差异就导致了完全不同的代码实现。3. 最长不下降序列问题实战3.1 问题分析与状态定义最长不下降序列Longest Non-decreasing Subsequence是动态规划的另一个经典应用。与背包问题不同这类序列问题通常需要考虑元素间的相对顺序。我第一次遇到这个问题时尝试用贪心算法解决结果发现无法保证全局最优。定义dp[i]为以第i个元素结尾的最长不下降子序列长度。这种定义方式能够很好地捕捉问题的子结构特性。状态转移方程需要向前寻找所有满足nums[j] nums[i]的jdp[i] max(dp[j] 1) for all j i and nums[j] nums[i]3.2 完整实现与序列追踪以下是带有序列追踪功能的C实现这也是面试中常考的进阶要求vectorint longestNonDecreasingSubsequence(vectorint nums) { int n nums.size(); vectorint dp(n, 1), parent(n, -1); int max_len 1, last_idx 0; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; parent[i] j; } } if (dp[i] max_len) { max_len dp[i]; last_idx i; } } vectorint result; while (last_idx ! -1) { result.push_back(nums[last_idx]); last_idx parent[last_idx]; } reverse(result.begin(), result.end()); return result; }实操心得parent数组的引入虽然增加了空间复杂度但在需要输出具体序列时必不可少。我在面试中被要求现场实现这个变种时最初版本只返回了长度后来才在面试官提示下补充了序列追踪功能。4. Hot100动态规划高频考题精讲4.1 股票买卖问题系列LeetCode Hot100中的股票买卖问题系列堪称动态规划应用的典范。这个系列包含六道难度递增的题目从最简单的单次交易到包含冷却期的多次交易。我在准备面试时曾专门用一周时间研究这个系列总结出了一套通用的分析框架。以最简单的买卖股票的最佳时机为例我们可以定义dp[i][0]表示第i天不持有股票的最大利润dp[i][1]表示第i天持有股票的最大利润。状态转移方程为dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) dp[i][1] max(dp[i-1][1], -prices[i])这个框架可以扩展到更复杂的情况。例如当交易次数限制为k次时我们需要增加一个维度来记录交易次数def maxProfit(k, prices): if not prices: return 0 n len(prices) dp [[[0]*2 for _ in range(k1)] for __ in range(n)] for i in range(n): for j in range(1, k1): if i 0: dp[i][j][0] 0 dp[i][j][1] -prices[i] else: dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) return dp[n-1][k][0]4.2 编辑距离问题另一个高频考题是编辑距离LeetCode 72它考察的是字符串间的动态规划处理能力。定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小操作数。状态转移需要考虑三种操作插入dp[i][j-1] 1删除dp[i-1][j] 1替换dp[i-1][j-1] (0 if word1[i-1] word2[j-1] else 1)实现代码如下def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]调试技巧在解决这类二维DP问题时我习惯先手动构建一个小规模的DP表格比如对horse和ros的转换过程。这种可视化方法能帮助快速发现状态转移中的逻辑错误。5. 动态规划优化技巧与常见误区5.1 空间复杂度优化大多数动态规划问题都可以进行空间优化。以斐波那契数列为例原始DP需要O(n)空间但实际上只需要保存前两个状态def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b对于二维DP问题空间优化通常需要分析状态转移的依赖关系。比如在01背包问题中我们通过逆序遍历实现了一维数组的优化。5.2 常见错误与排查方法在动态规划实践中我踩过不少坑总结出几个典型错误模式初始条件错误忘记初始化dp数组边界条件。比如在编辑距离问题中dp[i][0]和dp[0][j]需要初始化为i和j。遍历顺序错误特别是在空间优化后内外层循环的顺序和方向会影响结果正确性。01背包必须逆序完全背包则需要正序。状态转移遗漏有时问题需要考虑多种转移可能性容易遗漏某些情况。比如在股票问题中忘记考虑冷冻期的情况。dp数组定义不当定义不清晰会导致状态转移难以表达。建议先明确dp[i]或dp[i][j]的具体含义再开始编码。排查DP问题时我通常会打印出小规模输入的完整dp表格检查边界条件的初始化验证状态转移方程是否覆盖所有可能性对于优化后的版本与原始DP进行结果比对5.3 记忆化搜索与DP的选择虽然大多数情况下迭代DP更高效但有些场景记忆化搜索递归缓存更直观。比如在解决不同的二叉搜索树II这类需要枚举所有可能解的问题时记忆化搜索的实现会更自然def generateTrees(n): memo {} def dfs(start, end): if start end: return [None] if (start, end) in memo: return memo[(start, end)] res [] for i in range(start, end1): left dfs(start, i-1) right dfs(i1, end) for l in left: for r in right: root TreeNode(i) root.left l root.right r res.append(root) memo[(start, end)] res return res return dfs(1, n) if n else []选择迭代DP还是记忆化搜索取决于问题特性和个人习惯。我通常会在白板上先尝试记忆化搜索确认逻辑正确后再考虑能否转为更高效的迭代DP。 
长河君 · 2026/10/28 2:45:31 · 阅读 1.2k 动态规划核心：背包问题与最长子序列实战解析
1. 动态规划基础与代码随想录Day33概览动态规划作为算法领域的核心思想在解决最优化问题时展现出独特优势。代码随想录Day33这一章节聚焦动态规划的第二部分主要涵盖背包问题及其变种的解题思路。我初次接触这部分内容时曾被各种背包变体搞得晕头转向直到理清了它们之间的递推关系才豁然开朗。背包问题本质上是资源分配问题的一个经典模型。想象你有一个容量有限的背包和若干具有不同重量与价值的物品需要决定装入哪些物品才能使总价值最大化。这个看似简单的问题背后却蕴含着动态规划最精髓的状态转移思想。在代码随想录的课程体系中Day33通常安排在动态规划基础概念讲解之后作为进阶内容出现。它承接着前面斐波那契数列、爬楼梯等入门例题开始向更复杂的实际问题过渡。这个阶段的学习重点从理解递归公式转向掌握如何构建完整的状态转移方程。关键提示动态规划解题的核心在于明确dp数组定义和状态转移逻辑。很多初学者容易直接跳入代码实现反而忽略了这最重要的思考过程。2. 背包问题核心框架解析2.1 01背包问题标准解法01背包是动态规划中最经典的入门问题其特点是每种物品只能选择放入1或不放入0背包一次。我仍记得第一次写出完整解法时的兴奋感——那种将抽象思维转化为具体代码的成就感令人难忘。定义dp数组时我们通常使用二维表示法dp[i][j]表示从前i件物品中选择放入容量为j的背包所能获得的最大价值。状态转移方程则体现着动态规划的精髓dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])这个方程的含义非常直观对于第i件物品我们有两种选择——不放入背包保持前i-1件物品的最优解或者放入背包则需要在前i-1件物品中寻找剩余容量j-weight[i]时的最优解再加上当前物品的价值。在实际编码中为了优化空间复杂度我们通常会使用一维数组进行状态压缩def knapsack_01(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]注意事项内层循环必须逆序遍历这是为了避免同一物品被多次计入。这是01背包问题最易错的细节之一我在初学时曾因此debug了整整一个下午。2.2 完全背包问题变体与01背包不同完全背包允许物品被无限次选取。这个变化看似微小却完全改变了状态转移的逻辑。我第一次尝试修改01背包代码来解决完全背包时发现结果总是出错后来才明白需要调整遍历顺序。完全背包的状态转移方程与01背包类似但因为物品可以重复选取所以不需要考虑i-1的状态dp[j] max(dp[j], dp[j - weight[i]] value[i])对应的Python实现只需要将内层循环改为正序即可def knapsack_complete(weights, values, capacity): dp [0] * (capacity 1) for i in range(len(weights)): for j in range(weights[i], capacity 1): dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[capacity]这个例子很好地展示了动态规划中定义决定实现的特点。同样的状态转移逻辑因为问题定义的微小差异就导致了完全不同的代码实现。3. 最长不下降序列问题实战3.1 问题分析与状态定义最长不下降序列Longest Non-decreasing Subsequence是动态规划的另一个经典应用。与背包问题不同这类序列问题通常需要考虑元素间的相对顺序。我第一次遇到这个问题时尝试用贪心算法解决结果发现无法保证全局最优。定义dp[i]为以第i个元素结尾的最长不下降子序列长度。这种定义方式能够很好地捕捉问题的子结构特性。状态转移方程需要向前寻找所有满足nums[j] nums[i]的jdp[i] max(dp[j] 1) for all j i and nums[j] nums[i]3.2 完整实现与序列追踪以下是带有序列追踪功能的C实现这也是面试中常考的进阶要求vectorint longestNonDecreasingSubsequence(vectorint nums) { int n nums.size(); vectorint dp(n, 1), parent(n, -1); int max_len 1, last_idx 0; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i] dp[j] 1 dp[i]) { dp[i] dp[j] 1; parent[i] j; } } if (dp[i] max_len) { max_len dp[i]; last_idx i; } } vectorint result; while (last_idx ! -1) { result.push_back(nums[last_idx]); last_idx parent[last_idx]; } reverse(result.begin(), result.end()); return result; }实操心得parent数组的引入虽然增加了空间复杂度但在需要输出具体序列时必不可少。我在面试中被要求现场实现这个变种时最初版本只返回了长度后来才在面试官提示下补充了序列追踪功能。4. Hot100动态规划高频考题精讲4.1 股票买卖问题系列LeetCode Hot100中的股票买卖问题系列堪称动态规划应用的典范。这个系列包含六道难度递增的题目从最简单的单次交易到包含冷却期的多次交易。我在准备面试时曾专门用一周时间研究这个系列总结出了一套通用的分析框架。以最简单的买卖股票的最佳时机为例我们可以定义dp[i][0]表示第i天不持有股票的最大利润dp[i][1]表示第i天持有股票的最大利润。状态转移方程为dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]) dp[i][1] max(dp[i-1][1], -prices[i])这个框架可以扩展到更复杂的情况。例如当交易次数限制为k次时我们需要增加一个维度来记录交易次数def maxProfit(k, prices): if not prices: return 0 n len(prices) dp [[[0]*2 for _ in range(k1)] for __ in range(n)] for i in range(n): for j in range(1, k1): if i 0: dp[i][j][0] 0 dp[i][j][1] -prices[i] else: dp[i][j][0] max(dp[i-1][j][0], dp[i-1][j][1] prices[i]) dp[i][j][1] max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]) return dp[n-1][k][0]4.2 编辑距离问题另一个高频考题是编辑距离LeetCode 72它考察的是字符串间的动态规划处理能力。定义dp[i][j]表示将word1的前i个字符转换为word2的前j个字符所需的最小操作数。状态转移需要考虑三种操作插入dp[i][j-1] 1删除dp[i-1][j] 1替换dp[i-1][j-1] (0 if word1[i-1] word2[j-1] else 1)实现代码如下def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0]*(n1) for _ in range(m1)] for i in range(m1): dp[i][0] i for j in range(n1): dp[0][j] j for i in range(1, m1): for j in range(1, n1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 return dp[m][n]调试技巧在解决这类二维DP问题时我习惯先手动构建一个小规模的DP表格比如对horse和ros的转换过程。这种可视化方法能帮助快速发现状态转移中的逻辑错误。5. 动态规划优化技巧与常见误区5.1 空间复杂度优化大多数动态规划问题都可以进行空间优化。以斐波那契数列为例原始DP需要O(n)空间但实际上只需要保存前两个状态def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n1): a, b b, a b return b对于二维DP问题空间优化通常需要分析状态转移的依赖关系。比如在01背包问题中我们通过逆序遍历实现了一维数组的优化。5.2 常见错误与排查方法在动态规划实践中我踩过不少坑总结出几个典型错误模式初始条件错误忘记初始化dp数组边界条件。比如在编辑距离问题中dp[i][0]和dp[0][j]需要初始化为i和j。遍历顺序错误特别是在空间优化后内外层循环的顺序和方向会影响结果正确性。01背包必须逆序完全背包则需要正序。状态转移遗漏有时问题需要考虑多种转移可能性容易遗漏某些情况。比如在股票问题中忘记考虑冷冻期的情况。dp数组定义不当定义不清晰会导致状态转移难以表达。建议先明确dp[i]或dp[i][j]的具体含义再开始编码。排查DP问题时我通常会打印出小规模输入的完整dp表格检查边界条件的初始化验证状态转移方程是否覆盖所有可能性对于优化后的版本与原始DP进行结果比对5.3 记忆化搜索与DP的选择虽然大多数情况下迭代DP更高效但有些场景记忆化搜索递归缓存更直观。比如在解决不同的二叉搜索树II这类需要枚举所有可能解的问题时记忆化搜索的实现会更自然def generateTrees(n): memo {} def dfs(start, end): if start end: return [None] if (start, end) in memo: return memo[(start, end)] res [] for i in range(start, end1): left dfs(start, i-1) right dfs(i1, end) for l in left: for r in right: root TreeNode(i) root.left l root.right r res.append(root) memo[(start, end)] res return res return dfs(1, n) if n else []选择迭代DP还是记忆化搜索取决于问题特性和个人习惯。我通常会在白板上先尝试记忆化搜索确认逻辑正确后再考虑能否转为更高效的迭代DP。