322. 零钱兑换给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。你可以认为每种硬币的数量是无限的。示例 1输入coins [1, 2, 5], amount 11输出3解释11 5 5 1示例 2输入coins [2], amount 3输出-1示例 3输入coins [1], amount 0输出0示例 4输入coins [1], amount 1输出1示例 5输入coins [1], amount 2输出2提示1 coins.length 121 coins[i] 2^31 - 10 amount 10^4如果求组合数就是外层for循环遍历物品内层for遍历背包。如果求排列数就是外层for遍历背包内层for循环遍历物品。每种硬币的数量是无限的可以看出是典型的完全背包问题。dp[j]凑足总额为j所需钱币的最少个数为dp[j]凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]考虑coins[i]所以dp[j] 要取所有 dp[j - coins[i]] 1 中最小的。递推公式dp[j] min(dp[j - coins[i]] 1, dp[j]);首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0;其他下标对应的数值呢考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。我们要凑齐amount就像是要爬上第amount级台阶。你手里有几种不同长度的“砖块”硬币面额coins。状态定义dp[j]代表到达第j级台阶所需的最少砖块数。初始状态dp[0] 0站在地面不需要砖块。其他位置先设为一个“不可能的高度”如amount 1或无穷大表示还没找到路径。当你站在第j级台阶时你怎么来的你可能是从j - coins[0]跳上来的也可能是从j - coins[1]跳上来的……为了步数最少你会看一眼这几个前置位谁用的步数最少你就选谁然后再加 1加上当前这一枚硬币。dp[j] min(dp[j], dp[j - coins[i]] 1)def coinChange(coins, amount): # 初始化 dp 数组初始值为 amount 1比任何可能的硬币数都大 dp [amount 1] * (amount 1) dp[0] 0 # 遍历每一种面额的硬币 for coin in coins: # 遍历背包由于每种硬币无限所以从 coin 开始正向遍历 for j in range(coin, amount 1): # 如果能通过当前硬币减少步数则更新 dp[j] min(dp[j], dp[j - coin] 1) # 如果 dp[amount] 还是初始值说明凑不出来 return dp[amount] if dp[amount] amount else -1279.完全平方数给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。示例 1输入n 12输出3解释12 4 4 4示例 2输入n 13输出2解释13 4 9提示1 n 10^4Gemini said这道题LeetCode 279. 完全平方数其实和你刚才问的“零钱兑换”本质上是完全一样的问题。如果你能理解零钱兑换这道题只需做个简单的“脑筋急转弯”金额amount变成了这里的整数n。硬币面额coins变成了所有小于等于 n 的完全平方数1,4,9,16,…。目标凑齐 n 所需的最少“完全平方数”个数。1. 核心思路动态规划 (DP)我们可以沿用完全背包的思路构建一个dp数组。定义状态dp[i]表示凑齐整数 i 所需的最少完全平方数个数。状态转移方程 假设我们正在计算dp[i]我们可以尝试减去一个完全平方数 j2。 那么有dp[i]min(dp[i],dp[i−j2]1) 其中 j2≤i。边界条件dp[0] 0凑齐 0 需要 0 个数。初始化由于要求最小值我们将dp数组初始化为无穷大或者n 1。2. 代码实现 (Python)import math def numSquares(n): # 1. 初始化 dp 数组最大值设为 n (全是1的情况) dp [i for i in range(n 1)] # 2. 预先计算出所有可能的“硬币”完全平方数 # 比如 n12squares [1, 4, 9] max_square_index int(math.sqrt(n)) 1 squares [i**2 for i in range(1, max_square_index)] # 3. 开始动态规划 for square in squares: for i in range(square, n 1): # 这里的逻辑和零钱兑换一模一样 dp[i] min(dp[i], dp[i - square] 1) return dp[n]139.单词拆分给定一个非空字符串 s 和一个包含非空单词的列表 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1输入: s leetcode, wordDict [leet, code]输出: true解释: 返回 true 因为 leetcode 可以被拆分成 leet code。示例 2输入: s applepenapple, wordDict [apple, pen]输出: true解释: 返回 true 因为 applepenapple 可以被拆分成 apple pen apple。注意你可以重复使用字典中的单词。示例 3输入: s catsandog, wordDict [cats, dog, sand, and, cat]输出: false想象你面前有一条长长的面包字符串s你想知道能不能把它切成几段且每一段都在菜单wordDict里。状态定义dp[i]表示字符串的前i个字符能否被拆分成功。dp[0] True空字符串默认可以被拆分。递推公式 如果要判断dp[i]前i个字符是否为True我们需要在0到i之间找一个切割点j如果前j个字符是可以拆分的即dp[j] True且剩余的部分s[j:i]从j到i的子串在字典wordDict中那么前i个字符就是可以拆分的dp[i] True。你可以把dp[i]看作是一个接力赛“如果接力棒能传到第j个位置dp[j]是真并且从第j到第i这一段路有人跑子串在字典里那么接力棒就能传到第i个位置。”公式表示dp[i] dp[j] check(s[j:i])其中 $0 \le j i$def wordBreak(s, wordDict): # 为了查找更快把 list 转成 set word_set set(wordDict) n len(s) # dp[i] 表示 s 的前 i 个字符是否可以拆分 dp [False] * (n 1) dp[0] True # 初始状态 # 遍历背包字符串的长度 for i in range(1, n 1): # 遍历物品分割点 j for j in range(i): # 如果 前 j 个能拼成且 [j, i] 这段也在字典里 if dp[j] and s[j:i] in word_set: dp[i] True break # 只要找到一种拆分方式dp[i] 就是 True跳出当前循环 return dp[n]关于多重背包你该了解这些https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%A4%9A%E9%87%8D%E8%83%8C%E5%8C%85.html背包问题总结篇https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html