代码随想录算法训练营第三十八天 | 322.零钱兑换 279.完全平方数 139.单词拆分

322. 零钱兑换

题目链接：322. 零钱兑换 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili

思路：输入：coins = [1, 2, 5], amount = 11  输出：3  解释：11 = 5 + 5 + 1

1.确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

2.确定递推公式

不放硬币i：背包容量为j，里面不放硬币i的最少硬币数是dp[i-1][j]

放硬币i：背包空出硬币i的容量后，背包容量为j-coins[i]，可重复取，取出硬币i后也可在[0,i]取；即最少有dp[i][j-coins[i]]+1（取出的硬币i）个硬币

二维dp[i][j]=min(dp[i-1][j],dp[i][j-coins[i]]+1)

一维递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标非0的元素都是应该是最大值，考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

代码如下：vector<int> dp(amount + 1, INT_MAX);  dp[0] = 0;

4.确定遍历顺序

遍历顺序为：coins（物品）放在外循环，target（背包）在内循环。且内循环正序。

5.举例推导dp数组

279.完全平方数

题目链接：279. 完全平方数 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili

思路：输入：n = 13  输出：2   解释：13 = 4 + 9

1.确定dp数组以及下标的含义

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

2.确定递推公式

要选择最小的dp[j]，和上题一样所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

3.dp数组初始化

dp[0]表示和为0的完全平方数的最小数量，dp[0]=0

dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。

4.确定遍历顺序

外层遍历物品，内层遍历背包

5.举例推导dp数组

139.单词拆分

题目链接：139. 单词拆分 - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili

思路：输入: s = "leetcode", wordDict = ["leet", "code"]  输出: true   

解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

1.确定dp数组以及下标的含义

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

2.确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

3.dp数组初始化

dp[i] 的状态依靠 dp[j]是否为true，dp[0]就是递推的根基，dp[0]一定要为true

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4.确定遍历顺序

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

求组合数就是外层for循环遍历物品，内层for遍历背包；

求排列数就是外层for遍历背包，内层for循环遍历物品；

本题排列： 先遍历 背包，再遍历物品。

5.举例推导dp[i]