动态规划进阶：背包问题与序列问题实战解析

1. 动态规划核心思想与代码随想录Day33解析动态规划作为算法领域的经典方法论在解决最优化问题时展现出独特优势。代码随想录Day33这一章节聚焦动态规划的第二部分进阶内容主要涵盖背包问题的变种与序列类问题的典型解法。作为刷过300动态规划题的过来人我认为这部分内容是区分算法新手与进阶者的关键分水岭。在实际面试中动态规划问题出现的频率高达35%根据2023年LeetCode企业题库统计其中背包问题与序列问题占比超过60%。许多学习者常陷入看题解恍然大悟自己动手寸步难行的困境其根本原因在于没有建立正确的解题思维框架。接下来我将结合代码随想录的精华内容拆解动态规划的核心套路与实战技巧。2. 背包问题深度剖析2.1 01背包问题的本质理解01背包问题是动态规划的入门必修课其经典描述为给定容量为W的背包和N个物品每个物品有重量w[i]和价值v[i]如何选择物品使背包中物品总价值最大关键突破点在于状态定义dp[i][j]表示前i个物品在容量j时的最大价值状态转移方程dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) # 不选或选第i个物品实际编码时常用空间优化版滚动数组def knapsack(W, weights, values): dp [0] * (W 1) for i in range(len(weights)): for j in range(W, weights[i] - 1, -1): # 逆向遍历 dp[j] max(dp[j], dp[j - weights[i]] values[i]) return dp[W]关键技巧内层循环必须逆向遍历否则会变成完全背包问题2.2 完全背包与多重背包变种完全背包物品无限取用只需调整遍历方向for j in range(weights[i], W 1): # 正向遍历 dp[j] max(dp[j], dp[j - weights[i]] values[i])多重背包物品有限定次数可转化为01背包# 二进制拆分优化 new_weights [] new_values [] for w, v, cnt in zip(weights, values, counts): k 1 while k cnt: new_weights.append(w * k) new_values.append(v * k) cnt - k k * 2 if cnt 0: new_weights.append(w * cnt) new_values.append(v * cnt) # 然后按01背包处理3. 序列问题实战技巧3.1 最长递增子序列(LIS)求序列长度与具体序列是常见变种def lengthOfLIS(nums): tails [] for num in nums: idx bisect.bisect_left(tails, num) if idx len(tails): tails.append(num) else: tails[idx] num return len(tails) # 输出具体序列需要记录路径 def LIS_with_path(nums): dp [1] * len(nums) prev [-1] * len(nums) for i in range(1, len(nums)): for j in range(i): if nums[j] nums[i] and dp[j] 1 dp[i]: dp[i] dp[j] 1 prev[i] j max_len max(dp) last dp.index(max_len) path [] while last ! -1: path.append(nums[last]) last prev[last] return max_len, path[::-1]3.2 编辑距离问题编辑距离是字符串处理的经典动态规划问题def minDistance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]4. 动态规划解题方法论4.1 问题分解四步法定义状态明确dp数组的含义确定转移分析状态间的依赖关系初始化设置边界条件确定遍历顺序保证计算当前状态时依赖的状态已计算4.2 常见错误排查数组越界检查转移时的索引范围初始化不全特别是多维dp的边界条件遍历顺序错误完全背包与01背包的内层循环方向不同状态转移遗漏所有可能情况都要考虑5. 高频面试题精讲5.1 分割等和子集LeetCode 416def canPartition(nums): total sum(nums) if total % 2 ! 0: return False target total // 2 dp [False] * (target 1) dp[0] True for num in nums: for j in range(target, num - 1, -1): dp[j] dp[j] or dp[j - num] return dp[target]5.2 零钱兑换LeetCode 322def coinChange(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for coin in coins: for j in range(coin, amount 1): dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -16. 动态规划优化技巧6.1 状态压缩当状态转移只依赖有限的前置状态时可使用滚动数组降低空间复杂度。例如斐波那契数列问题def fib(n): if n 2: return n a, b 0, 1 for _ in range(2, n 1): a, b b, a b return b6.2 记忆化搜索自顶向下的递归解法配合缓存from functools import lru_cache lru_cache(maxsizeNone) def fib(n): if n 2: return n return fib(n-1) fib(n-2)7. 动态规划学习路线建议基础阶段2周掌握斐波那契、爬楼梯等线性DP理解01背包、完全背包的区别练习最少硬币、分割等和子集问题进阶阶段3周攻克LIS、LCS等序列问题学习树形DP如打家劫舍III理解状态压缩技巧强化阶段持续每日精做2道动态规划题参加周赛锻炼实战能力定期复习经典题型的变种在刷题过程中建议建立自己的错题本记录每道题的初始思路误区正确的状态定义关键的转移方程易错的边界条件我个人的经验是动态规划能力的突破往往发生在系统刷完50道经典题型后。当你能在看到新题时快速识别出这是背包问题的变种或这需要二维状态定义就标志着已经掌握了动态规划的核心思维。