代码随想录训练营 Day38打卡 动态规划 part06 322. 零钱兑换 279. 完全平方数 139. 单词拆分

代码随想录训练营 Day38打卡 动态规划 part06

一、力扣322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。

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]);

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。

所以本题并不强调集合是组合还是排列。

以输入：coins = [1, 2, 5], amount = 5为例

dp[amount]为最终结果。

代码实现

class Solution:def coinChange(self, coins: List[int], amount: int) -> int:# 创建一个长度为 amount + 1 的 dp 数组，初始值为正无穷大（表示当前金额不可达）dp = [float('inf')] * (amount + 1)# 初始化 dp[0] 为 0，因为凑出金额 0 需要 0 个硬币dp[0] = 0# 遍历每一种硬币面额for coin in coins:  # 遍历硬币，相当于遍历物品# 对于当前硬币面额 coin，遍历背包容量从 coin 到 amountfor i in range(coin, amount + 1):  # 遍历背包容量# 如果 dp[i - coin] 不是正无穷大，表示金额 (i - coin) 可达if dp[i - coin] != float('inf'):# 更新 dp[i]，取使用当前硬币和不使用当前硬币两种情况中的最小值dp[i] = min(dp[i - coin] + 1, dp[i])# 检查 dp[amount] 是否仍为正无穷大# 如果是，则表示没有办法凑出总金额，返回 -1if dp[amount] == float('inf'):return -1# 否则，返回凑出总金额所需的最少硬币个数return dp[amount]

力扣题目链接
题目文章讲解
题目视频讲解

二、力扣279. 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 ：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？

dp[j]：和为j的完全平方数的最少数量为dp[j]

dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。

此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

已输入n为5例，dp状态图如下：

最后的dp[n]为最终结果。

class Solution:def numSquares(self, n: int) -> int:# 初始化 dp 数组，长度为 n + 1，初始值为正无穷大# dp[j] 表示和为 j 的完全平方数的最少数量dp = [float('inf')] * (n + 1)# dp[0] = 0，因为和为 0 需要 0 个完全平方数dp[0] = 0# 遍历所有可能的完全平方数for i in range(1, int(n ** 0.5) + 1):  # i 表示当前完全平方数的根，如 1, 2, 3, ..., sqrt(n)square = i * i  # 计算完全平方数# 遍历背包容量（即要凑的目标和）for j in range(square, n + 1):  # j 表示当前目标和，从 square 到 n# 更新 dp[j]，选择使用当前完全平方数后的最小值dp[j] = min(dp[j - square] + 1, dp[j])# 返回和为 n 的完全平方数的最少数量return dp[n]

力扣题目链接
题目文章讲解
题目视频讲解

三、力扣139. 单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 ：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包！

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

而本题其实我们求的是排列数，为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。

“apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。

以输入: s = “leetcode”, wordDict = [“leet”, “code”]为例，dp状态如图：

dp[s.size()]就是最终结果。

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:# 将 wordDict 转换为一个集合，以便更快速地进行单词查找操作wordSet = set(wordDict)n = len(s)  # 获取字符串 s 的长度# 创建一个长度为 n + 1 的 dp 数组# dp[i] 表示字符串 s 的前 i 个字符是否可以被拆分成字典中的单词dp = [False] * (n + 1)# dp[0] 表示空字符串，空字符串被认为可以被拆分成字典中的单词dp[0] = True# 遍历字符串的每个位置 i（从 1 到 n），相当于动态规划中的“背包容量”for i in range(1, n + 1):# 对于每个位置 i，检查从 0 到 i 的所有前缀 s[0:j] 是否可以被拆分for j in range(i):# 如果 s 的前 j 个字符可以被拆分成单词（dp[j] 为 True）# 并且 s[j:i] 这一段字符串在 wordSet 中存在，则 dp[i] 也为 Trueif dp[j] and s[j:i] in wordSet:dp[i] = True  # 更新 dp[i] 为 True，表示 s[0:i] 可以被拆分成字典中的单词break  # 找到一个有效拆分后，停止当前循环，进入下一个 i# 最后返回 dp[n]，即字符串 s 的前 n 个字符（即整个字符串）是否可以被拆分成字典中的单词return dp[n]

力扣题目链接
题目文章讲解
题目视频讲解