代码随想录第38天|完全背包
322.零钱兑换
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
代码随想录
第一想法：
经过自己画图之后，如下：
- dp[ j ]含义 ：装满 j 所需的最少硬币数为 dp [ j ]
- 递推公式 : dp [ j ] = min (dp[ j ] ,dp [ j - coins[i] ]+1)
- 初始化 :
- dp [ 0 ] = 0;
- 非零元素 全部初始化为 最大值
- 遍历顺序
- 这是一个组合问题，所以先遍历物品，再遍历背包
- 若 dp[ amount] ==Max || dp[amount] ==0 ,返回-1
代码：
class Solution {public int coinChange(int[] coins, int amount) {int[] dp = new int[amount+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] = 0;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {if(dp[j-coins[i]]!=Integer.MAX_VALUE){//只有dp[j-coins[i]]不是初始最大值时，才有选择的必要否则就是。Max+1溢出直接变成最小值。dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);}}}return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];}
}279.完全平方数
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
代码随想录
第一想法：
这道题和上面的题是一样的。但是特别注意两种写法是不一样的。
代码：
class Solution {public int numSquares(int n) {int[] dp = new int[n+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] = 0;for (int j = 1; j <= n; j++) {for (int i = 1; i * i <= j; i++) {dp[j] = Math.min(dp[j],dp[j-i*i]+1);}}return dp[n]==Integer.MAX_VALUE?-1:dp[n];}
}139.单词拆分
视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili
代码随想录
代码随想录
- dp[j]:字符串长度为j时，dp[j] = true,表示可以被拆分成多个在字典中出现的单词
- 递推公式： if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
- 初始化 : dp[0] = true
- 遍历顺序： 排序问题，先遍历背包，再遍历物品
代码
class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp = new boolean[s.length()+1];dp[0] = true;for (int i = 1; i <= s.length(); i++) {for (String word : wordDict) {int length = word.length();if(i>=length&&dp[i-length]&&word.equals(s.substring(i-length,i))){dp[i]=true;break;}}}return dp[s.length()];}
}