代码随想录算法训练营第三十三天：零钱兑换，完全平方数，单词拆分
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 <= 12
- 1 <= coins[i] <= 2^31 - 1
- 0 <= amount <= 10^4
思路：
本题描述里提到了每种硬币都是无限的，所以是典型的完全背包问题，直接动规五部曲
1.dp数组及其下标的含义：dp[j]代表总金额j所需钱币最少数量为dp[j]
2.确定递推公式：凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]，所以递推公式就是dp[j] = min（dp[j - coins[i]] + 1, dp[j]）
3.dp数组如何初始化：首先dp[0]就得等于0，其次就是其他非零下标都得赋值为正无穷，因为dp公式是靠min不断更新，正无穷是为了防止在比较的过程中dp[j]被初始值覆盖。
4.确定遍历顺序：昨天我们写了求组合的，还写了求排列的，这俩遍历顺序是有讲究的：组合是外物品内背包，排列是外背包内物品。但是本题只是求最少几枚币，两个哪个都不算，所以用哪个都可以，都是对的
5.举例推导dp数组
以输入：coins = [1, 2, 5], amount = 5为例
dp[amount]为最终结果。
代码示例：
function coinChange(coins: number[], amount: number): number { const dp:number[] = new Array(amount + 1).fill(Infinity) dp[0] = 0 for(let i = 0; i < coins.length; i++){ for(let j = coins[i]; j <= amount; j++){ if(dp[j - coins[i]] === Infinity) continue dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1) } } return dp[amount] === Infinity ? -1 : dp[amount] };279.完全平方数
文章讲解/视频讲解
题目描述：
给定正整数 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^4
思路：
本题跟上题基本没啥区别，乍看感觉挺麻烦的，但是其实翻译一下：完全平方数就是物品，还是无限用的，正整数n就是背包容量，问凑满这个背包容量为n的背包需要多少个物品（完全平方数）。
1.确定dp数组及其下标的含义：dp[j]代表和为j的正整数最少需要dp[j]个完全平方数
2.确定递推公式：和上题保持一致：dp[j] = min（dp[j - coins[i]] + 1, dp[j]），原因都是一样一样的，把钱币替换成完全平方数就是了
3.dp数组的初始化：依旧是dp[0] = 0，其他非零下标要初始化为正无穷，原因同上
4.确定遍历顺序：这个也是一样的，本题求的只是最少用几个完全平方数，没问有几种，所以先遍历物品还是先遍历背包都是一样的，上题先遍历物品，这题就先遍历背包了
5.举例推导dp数组
已输入n为5例，dp状态图如下：
dp[0] = 0 dp[1] = min(dp[0] + 1) = 1 dp[2] = min(dp[1] + 1) = 2 dp[3] = min(dp[2] + 1) = 3 dp[4] = min(dp[3] + 1, dp[0] + 1) = 1 dp[5] = min(dp[4] + 1, dp[1] + 1) = 2
最后的dp[n]为最终结果。
代码示例：
function numSquares(n: number): number { const dp:number[] = new Array(n + 1).fill(Infinity) dp[0] = 0 for(let i = 1; i <= n; i++){ for(let j = 1; j * j <= i; j++){ dp[i] = Math.min(dp[i], dp[i - j * j] + 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就是背包，问我们能不能用物品（单词）装满背包（字符串s），单词是可以重复使用的，毫无疑问的完全背包。
1.dp数组及其下标含义：dp[i]为true表示，长度为i的字符串可以被拆封成一个或者多个单词，换句话就说字符串s的前i个字符是否能被拆分
2.确定递推公式：切割的范围是[j，i]，我们要确保[j,i]切割出来是个单词，还得确保dp[j] === true（字符串前j个字符可以被拆分成单词），只有两个条件都满足，我们才把当前dp[i]修改为true，递推公式为：if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3.dp数组如何初始化：dp[0]是整个遍历过程的基石，也是遍历的开始，如果dp[0]为false，后续所有的dp[i]都不可能为true，因为满足不了“dp[j]是true”这个关键条件。所以dp[0]一定要初始化为true，其他非零下标初始化为false即可
4.确定遍历顺序：又要开始讨论本题到底是组合还是排列问题了，我们来回顾一下组合和排列，以1,5和5,1为例，这两个算一个组合，但是算两种排列。而本题是排列问题：
拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。
"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。
"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。
强调物品顺序正是排列的重要特征，所以本题的遍历顺序是外层遍历背包容量，内层遍历物品
5.举例推导dp[i]
以输入: s = "leetcode", wordDict = ["leet", "code"]为例，dp状态如图：
dp[s.size()]就是最终结果。
代码示例：
function wordBreak(s: string, wordDict: string[]): boolean { const dp:boolean[] = new Array(s.length + 1).fill(false) dp[0] = true for(let i = 1; i <= s.length; i++){ for(let j = 0; j < i; j++){ let temp:string = s.slice(j,i) if(wordDict.includes(temp) && dp[j] === true){ dp[i] = true } } } return dp[s.length] };