1. 项目概述今天要分享的是代码随想录算法训练营第38天的学习内容主要涉及四个经典动态规划问题322.零钱兑换、279.完全平方数、139.单词拆分以及多重背包问题。这几个题目在面试中出现的频率相当高也是动态规划学习的必经之路。作为算法训练营的老学员我发现这几个题目虽然表面看起来各不相同但核心思路都是动态规划的经典应用场景。通过系统性的训练可以帮助我们建立起解决这类问题的思维框架。下面我就结合自己的刷题经验详细拆解每个问题的解题思路和实现细节。2. 核心问题解析2.1 322. 零钱兑换零钱兑换是动态规划中的经典问题给定不同面额的硬币和一个总金额计算可以凑成总金额所需的最少硬币数。如果没有任何一种硬币组合能组成总金额返回-1。这个问题的关键在于理解状态转移方程。我们可以定义一个dp数组其中dp[i]表示组成金额i所需的最少硬币数。对于每个金额i我们遍历所有硬币面额coin如果coin i那么dp[i] min(dp[i], dp[i - coin] 1)。注意初始化时dp[0] 0其他位置可以初始化为一个较大的值如amount1表示初始状态下无法凑出该金额。2.2 279. 完全平方数完全平方数问题要求找出组成一个正整数n的最少数量的完全平方数之和。例如12可以由444组成也可以由9111组成但最优解是444只需要3个完全平方数。这个问题可以转化为背包问题其中背包容量是n物品是完全平方数。我们可以使用动态规划来解决定义dp[i]表示组成整数i所需的最少完全平方数数量。状态转移方程为dp[i] min(dp[i], dp[i - jj] 1)其中jj i。这个问题的优化空间在于可以预先生成所有可能的完全平方数。2.3 139. 单词拆分单词拆分问题给定一个非空字符串s和一个包含非空单词列表的字典wordDict判断s是否可以被拆分为一个或多个字典中的单词。这个问题同样可以使用动态规划解决。定义dp[i]表示字符串前i个字符能否被拆分成字典中的单词。状态转移方程为对于每个j i如果dp[j]为true且s.substring(j, i)在字典中那么dp[i]也为true。实操技巧为了提高效率可以先找出字典中最长单词的长度这样在遍历时可以减少不必要的检查。2.4 多重背包问题多重背包问题是背包问题的变种其中每种物品有数量限制。与完全背包无限数量和01背包每种物品只有一个不同多重背包更接近现实场景。解决多重背包问题的经典方法是将它转化为01背包问题。具体来说可以将每种物品拆分成多个独立的物品每个物品的数量为1。不过这种方法在物品数量很大时效率不高。更优的解法是使用二进制优化将每种物品的数量拆分成1,2,4,...,2^k的组这样可以用更少的物品表示所有可能的数量组合。例如13可以拆分为1,2,4,6因为124613。3. 解题思路与实现细节3.1 零钱兑换的实现def coinChange(coins, amount): dp [amount 1] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount 1): dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! amount 1 else -1这个实现有几个关键点初始化dp数组时使用amount1作为无穷大的表示外层循环遍历硬币面额内层循环更新dp数组最后检查dp[amount]是否被更新过3.2 完全平方数的优化实现def numSquares(n): square_nums [i**2 for i in range(1, int(n**0.5)1)] dp [float(inf)] * (n 1) dp[0] 0 for i in range(1, n 1): for square in square_nums: if square i: break dp[i] min(dp[i], dp[i - square] 1) return dp[n]优化点预先生成所有可能的完全平方数当平方数大于当前i时提前终止内层循环使用float(inf)表示初始不可达状态3.3 单词拆分的边界处理def wordBreak(s, wordDict): word_set set(wordDict) max_len max(len(word) for word in wordDict) if wordDict else 0 dp [False] * (len(s) 1) dp[0] True for i in range(1, len(s) 1): for j in range(max(0, i - max_len), i): if dp[j] and s[j:i] in word_set: dp[i] True break return dp[len(s)]关键优化将wordDict转换为集合提高查找效率记录最长单词长度减少不必要的检查一旦找到匹配就立即break内层循环3.4 多重背包的二进制优化def multipleKnapsack(weights, values, counts, capacity): # 二进制优化处理 new_weights [] new_values [] for w, v, c in zip(weights, values, counts): k 1 while k c: new_weights.append(w * k) new_values.append(v * k) c - k k * 2 if c 0: new_weights.append(w * c) new_values.append(v * c) # 01背包问题 dp [0] * (capacity 1) for w, v in zip(new_weights, new_values): for i in range(capacity, w - 1, -1): dp[i] max(dp[i], dp[i - w] v) return dp[capacity]二进制优化的核心思想将每种物品的数量拆分为1,2,4,...,2^k的组剩余部分单独作为一组转化为01背包问题求解4. 常见问题与调试技巧4.1 零钱兑换的边界条件常见错误忘记处理无法兑换的情况初始化dp数组时值设置不当硬币面额包含0的情况题目通常不会出现调试技巧打印dp数组的中间状态观察变化过程从小例子开始如coins[1,2,5], amount54.2 完全平方数的数学优化除了动态规划这个问题还可以用数学方法解决。根据拉格朗日四平方定理任何自然数都可以表示为不超过4个完全平方数的和。这意味着答案只可能是1,2,3或4。基于这个定理我们可以先检查n是否是完全平方数返回1然后检查是否可以表示为两个平方数之和最后再尝试3的情况。4.3 单词拆分的性能优化当字典很大时简单的实现可能会超时。可以考虑以下优化使用Trie树存储字典加速字符串匹配记忆化搜索替代动态规划预处理字典建立字符到单词的映射4.4 多重背包的空间优化与01背包类似多重背包也可以优化空间复杂度。可以使用一维数组并逆序遍历dp [0] * (capacity 1) for i in range(len(weights)): for j in range(capacity, weights[i] - 1, -1): for k in range(1, min(counts[i], j // weights[i]) 1): dp[j] max(dp[j], dp[j - k * weights[i]] k * values[i])这种实现虽然空间优化了但时间复杂度较高适用于容量不大的情况。5. 总结与个人心得通过这几个题目的训练我对动态规划有了更深的理解。特别是多重背包问题让我认识到如何将复杂问题转化为已知的简单问题。在实际刷题过程中我发现以下几点特别重要定义清晰的状态表示dp[i]到底代表什么一定要明确正确处理边界条件特别是初始化和无法达成的情况学会问题转化很多问题都可以转化为背包问题的变种优化意识不仅要写出解法还要思考如何优化时间和空间动态规划确实需要大量练习才能掌握建议从简单的题目开始逐步增加难度。对于每个做过的题目最好能写下解题思路和心得体会这样进步会更快。
