代码随想录Day39|322. 零钱兑换、279.完全平方数、139.单词拆分
322. 零钱兑换
dp[j]：装满容量为j的背包的最小元素个数。
递推公式：dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
初始化：dp[0] = 0,因为要取最小值，所以待更新的区域都初始化成最大值。
遍历顺序：因为不强调组合还是排列，只是求元素个数。
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];int max = Integer.MAX_VALUE -1;for(int i = 1; i<=amount;i++){dp[i] = max;}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],dp[j-coins[i]]+1);}}}return max == dp[amount]? -1:dp[amount];}
}279.完全平方数
这题是自己用了个类似于查表法的思路，生成了个平方数的数组。看了题解后觉得自己很呆。
dp[j]：装满容量为j的背包的最小元素个数。
递推公式：dp[j] = Math.min(dp[j],dp[j-nums[i]]+1);
初始化：dp[0] = 0,因为要取最小值，所以待更新的区域都初始化成最大值。
遍历顺序：因为不强调组合还是排列，只是求元素个数。
class Solution {public int numSquares(int n) {int[] nums = new int[101];for(int i = 1; i <nums.length;i++){nums[i] = i*i;}int[] dp = new int[n+1];int max = Integer.MAX_VALUE;for(int i = 1; i <=n; i++){dp[i] = max;}for(int i = 1; i < nums.length; i++){for(int j = 1; j<=n; j++){if(j - nums[i] >=0){dp[j] = Math.min(dp[j],dp[j-nums[i]] + 1);}}}return dp[n];}
}139.单词拆分
个人觉得这题不太好理解，但是好像其他同学觉得不难。
dp[i] : 背包为i容量，这里应该必须是从字符串的[0,i],能用字典单词组合成功为true，否则为false。
递推公式：dp[i] = set.contains(substring[j,i]) && dp[j]
这里dp[j]是加新单词之前的状态，如果新单词能找到，新单词之前的字符串也能找到，才输出dp[i]=true。
注意要判断下，再进入递归公式，有可能dp[i]本来已经为true了，但是新截取的字符串构不成单词，又给赋值成false了，所以不要每次都赋值。只要改过一次为true了就说明[0,i]是可以组合成功的。
遍历顺序：组合数，外层遍历背包。
初始化：dp[0] = true，其他都是false
class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<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;i > j;j++){if(set.contains(s.substring(j,i)) && dp[j]){dp[i]= true;}}}return dp[s.length()];}
}