Day38补20250117代码随想录动态规划6 322.零钱兑换|279.完全平方数|139.单词拆分|多重背包问题|总结
【多重背包问题】稍微了解了一下，没有具体敲代码
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
提示：
1 <= coins.length <= 121 <= coins[i] <= 2<sup>31</sup> - 10 <= amount <= 10<sup>4</sup>
思路
- 518.零钱兑换II 求的是【凑成总金额的硬币组合数(求有几种组合方法)】，这题求的是【所需的最少硬币个数(求的是最少个数)】。
- 五部曲
- 定义，dp[j]表示的是在背包容量为j时需要的最少硬币个数。
- 递进，求最小硬币个数，dp[j]=Math.min(dp[j],dp[j-coins[i]]+1); //coins代表weight,value代表什么？ value=1;
- 初始化，Integer.MAX_VALUE,dp[0]=0,除此之外，都设置为MAX_VALUE。
- 遍历顺序,组合和排列都不影响最终的结果。
- 打印数组
- 代码
class Solution {public int coinChange(int[] coins, int amount) {int m=coins.length;int max=Integer.MAX_VALUE;int[] dp=new int[amount+1];for(int j=0;j<dp.length;j++){dp[j]=max;}dp[0]=0;for(int i=0;i<m;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 dp[amount]==max?-1:dp[amount];//dp仍然是最大值，说明无解 } }
总结
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。
- 低级错误，intn=amount.length; amount本来就是一个常数，犯错第二次了！！！！
- 注意必须初始化为0，如果dp全为MAX，无法正确迭代
- 必须加判断条件，当dp[j-coins[i]]为max，不进行迭代，否则会出错。反例：如果某个j面值无法通过硬币组合凑成，那么就是MAX_VALUE。那么就应该跳过这个判断，例如dp[2]=max,dp[7-5]也是max，max和max比较是无意义的递推。
- 如果不加判断条件，会导致INT溢出，max+1。
题目
给你一个整数 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次方
思路
-
我的思路 五部曲
- 定义，dp[j]为返回的最小数量，背包容量j<=n,物品i为完全平方数，weight范围为[1,10^2]的平方，
- 递进，dp[j]=Math.min(dp[j],dp[j-weight[i]]+value[i]);//value=1
- 初始化，dp[0]=0;
- 遍历顺序，可以重复加，先遍历物品，再遍历背包
- 打印数组，
-
我的代码
class Solution {public int numSquares(int n) {int[] dp=new int[n+1];int max=Integer.MAX_VALUE;for(int j=0;j<=n;j++){dp[j]=max;}dp[0]=0;int[] full=new int[n];//[1,n] n种容量for(int i=0;i<=n-1;i++){full[i]=(i+1)*(i+1);for(int j=full[i];j<=n;j++){if(dp[j-full[i]]!=max){dp[j]=Math.min(dp[j],dp[j-full[i]]+1);} } }return dp[n];} } -
Carl优化思路，少用一个数组
class Solution {public int numSquares(int n) {int[] dp=new int[n+1];int max=Integer.MAX_VALUE;for(int j=0;j<=n;j++){dp[j]=max;}dp[0]=0;for(int i=1;i*i<=n;i++){for(int j=i*i;j<=n;j++){if(dp[j-i*i]!=max){dp[j]=Math.min(dp[j],dp[j-i*i]+1);} } }return dp[n]; } }
总结
- dp数组的数组长度为n+1，j包含0
- 和上一题几乎一样
139.单词拆分
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意： 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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
提示：
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
思路
-
五步
- 定义，valid[i],i表示字符串长度，dp如果是true,表示可以拆分
- 递推
- if[i,j]这个区间的字串出现在字典里&&dp[i]=true，dp[j]=true;
- 2
- 遍历顺序，有顺序，先遍历背包，再遍历物品
-
代码
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 j=1;j<=s.length();j++){//背包，遍历字符串，for(int i=0;i<j&&!dp[j];i++){//当valid=false才继续递归，递归完成内层循环不再执行if(set.contains(s.substring(i,j))&&dp[i]){//valid[j]之前是可以拆分的，且物品包含字符串的[j,i]中的字母dp[j]=true;//0到j}}}return dp[s.length()];} }
总结
- 用法
- s.substring(i,j)切割区间为i,j
- set.contains，物品是否包含在字符串里
- 一做字符串就迷糊，需要找个时间集中攻克。
- 条件略显复杂
- 遍历物品时，for(int i=0;i<j&&!dp[j];i++){//当valid=false才继续递归，递归完成内层循环不再执行
- 当确认包含后，说明可以切分。if(set.contains(s.substring(i,j))&&dp[i]){//valid[j]之前是可以拆分的，且物品包含字符串的[j,i]中的字母
dp[j]=true;//0到j
}
多重背包问题
- 有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用(平摊后即为01背包问题)，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
背包问题总结
https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html#%E8%83%8C%E5%8C%85%E9%80%92%E6%8E%A8%E5%85%AC%E5%BC%8F
