代码随想录|动态规划 322. 零钱兑换 279.完全平方数 139.单词拆分
322. 零钱兑换
题目
参考文章
思路：本题其实也是完全背包问题
dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
但是在初始化dp数组时，要初始化为最大的值，因为从题目知道，要得到的是最少的硬币个数，所以在取min时，为了防止会被初始值覆盖的风险，得把初始值设置为最大值
递推公式：dp[j]=min(dp[j-conis[i]]+1,dp[j]);
这里为什么是 +1 呢？因为题目是求硬币个数，所以要把当前的硬币加上，就直接加1即可。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题不强调排列或组合
代码：
class Solution {
public int coinChange(int[] coins, int amount) {
int max=Integer.MAX_VALUE;
int[] dp=new int[amount+1];
for(int i=0;i<=amount;i++){
dp[i]=max;
}
dp[0]=0;
for(int i=0;i<coins.length;i++){
for(int j=coins[i];j<=amount;j++){
if(dp[j-coins[i]]!=max){//只有当要取的数组值不是最大值，最后得到的最小值才有意义
dp[j]=Math.min(dp[j-coins[i]]+1,dp[j]);
}
}
}
return dp[amount]==max?-1:dp[amount];
}
}279.完全平方数
题目
参考文章
思路：本题思路和 322零钱兑换相似。也是求最少数量，仍初始化dp数组为最大值。然后一次次的最最小值。
同时有因为完全平方数中有 1 所以无论什么数，都可以由1拼凑出来
代码：
class Solution {
public int numSquares(int n) {
int max=Integer.MAX_VALUE;
int[] dp=new int[n+1];
for(int i=0;i<=n;i++){
dp[i]=max;
}
dp[0]=0;
for(int i=1;i*i<=n;i++){//因为由题目知道，其要的是完全平方数，所以直接把 i*i作为当前的物品，n为背包容量
for(int j=i*i;j<=n;j++){
dp[j]=Math.min(dp[j-i*i]+1,dp[j]);
}
}
return dp[n];
}
}139.单词拆分
题目
参考文章
思路：单词就是物品，字符串s就是背包
dp数组含义 ：dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true （j<i）
dp[0]表示如果字符串为空的话，说明出现在字典里
dp[0]=true,其他的为false
本题要求的是排列数，为什么呢？因为在字典集中，同样的单词组，如果顺序变了，它最后得到的字符都是不一样的，所以强调排列数。
排列数（即使是相同元素，但是顺序不同，也作为一个分组）
组合数（把相同元素的都认为只有一个组）
这里j<i,是因为我们后面要取s中从j到i位置的字符是否在set集合中，如果在就表示可以组成，把当前的点改为true
这里的dp[j]其实就是说，前一个单词比较的时候，是确定可以组成一个s的一部分的，才可以设置下一个也可以组成s的一部分，如果dp[j]的时候都不能组成s的一部分，这里即使单词配对正确，也是不能得到s字符串
代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set=new HashSet<>(wordDict);
boolean[] dp=new boolean[s.length()+1];
dp[0]=true;
for(int i=1;i<=s.length();i++){//先遍历背包
for(int j=0;j<i&&!dp[i];j++){//再遍历物品，这里j<i,是因为我们后面要取s中从j到i位置的字符是否在set集合中，如果在就表示可以组成，把当前的点改为true
if(set.contains(s.substring(j,i))&&dp[j]){//这里的dp[j]其实就是说，前一个单词比较的时候，是确定可以组成一个s的一部分的，才可以设置下一个也可以组成s的一部分，如果dp[j]的时候都不能组成s的一部分，这里即使单词配对正确，也是不能得到s字符串
dp[i]=true;
}
}
}
return dp[s.length()];
}
}