377 组合总和Ⅱ
题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
题目中说到：从 nums 中找出并返回总和为 target 的元素组合的个数。 但是后面又紧跟着说顺序不同的作为不同的组合。 那么本题就不能看成单纯的组合数 ，而是排列。因为排列对于顺序有要求， 所以需要按照排列的思维去思考同时还需要有动态规划的思考。 这就是这道题难的地方。
按照动规的思路dp[i] : 表示总和为i的组合的个数为dp[i]
还有需要注意的就是遍历的顺序， 一般来说对于背包问题：
**求组合是外层遍历物品，内层遍历背包。 **
求排列是外层遍历背包，内层遍历物品。
所以，本题我们也是采用这种遍历方式进行。
实现
class Solution { public int combinationSum4(int[] nums, int target) { //如果求组合数就是外层for循环遍历物品，内层for遍历背包。 // 如果求排列数就是外层for遍历背包，内层for循环遍历物品。 int []dp = new int[target+1]; dp[0] = 1; //外层遍历背包 for(int j = 0; j <= target;j++){ //内层遍历物品 for(int i =0 ;i < nums.length;i++){ //如果被当前背包的容量 >= 物品的重量， 那么就进行递推。 否则就遍历下一个数 if( j >= nums[i] ){ //求组合数使用 += 求最大值/最小值 使用max/min dp[j] += dp[j-nums[i]]; } } } return dp[target]; } }
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 <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
思路
本题和我们之前做的零钱总换(地址: https://wclspace.xyz/post/4ee41ff3.html#518-%E9%9B%B6%E9%92%B1%E6%80%BB%E6%8D%A2)是一个类型的题， 上一道这个题是要求返回凑成总金额的组合数， 而本题是返回可以凑成总金额所需的最少的硬币个数 所以这两道题在递推公式上略有不同。
dp[i]:表示 可以凑成总金额 i 所需的 最少的硬币个数为dp[i]
这道题对于遍历的位次顺序要求就没那么高了， 先遍历背包或者物品都行 ，这里我用先遍历物品（习惯）。同时， 因为对于数组中的银币的数量是无限制的， 所以我们可以一直使用同一个， 所以在内层遍历背包的时候需要正序遍历， 这样就可以保证同一个硬币被多次使用了。
注意： 因为要获取最少的硬币个数 ，所以在初始化dp数组的时候需要将其赋予最大值， 这样才能再每次递推的时候获取最小值（也就是最少使用硬币个数）
对于dp[0]的初始化，这里给dp[0] = 0，按照题意总金额为 0的个数也是 0 。 所以可以赋值为0 ， 至于其他的， 我们需要赋值为最大值 ，原因上面有说
实现
class Solution { public int coinChange(int[] coins, int amount) { //题目要求 : 返回可以凑成总金额所需的 最少的硬币个数 int []dp = new int[amount +1]; //dp[i] 表示 凑成总金额为i所需要的最少硬币数为 dp[i] //需要计算最大的硬币面值 for(int i = 0;i < dp.length; i++){ dp[i] = Integer.MAX_VALUE; } //初始化dp[0] = 0 if amount == 0 then dp[0] = 0 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] = Math.min(dp[j], dp[j-coins[i]] +1); } } } return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount]; } }
279 完全平方数
题目
给你一个整数 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 <= 104
思路
题中要求: 返回和为 n的完全平方数的最少数量
所以**dp[i]: 可以表示 和为 i 的完全平方数的最少数量是dp[i]**
遍历顺序还是使用先物品 后背包的方式， 如果物品的重量 > 背包的容量。 那么就直接continue， 否则就进行递推公式
for(int i= 1; i*i <= n; i++){ for(int j = i*i; j<= n; j++) }
因为本题需要的是最数量， 所以我们在初始化dp[i]的时候， 需要将其赋值为MAX_VALUE， 这样才能实现min(dp[j],dp[j-i*i] + 1)的时候取最小值。 同时对于dp[0] =0 因为 和为 0 的完全平方数最少数量本来就是 0
实现
class Solution { public int numSquares(int n) { int []dp = new int[n+1]; //dp[i]： dp数组的含义是 和为整数i的 完全平方数最少数量为dp[i] for(int i =0 ;i <= n; i++){ dp[i] = Integer.MAX_VALUE; } dp[0] = 0; for(int i = 1; i*i <= n;i++){ for(int j = i*i; j <= n;j++){ dp[j] = Math.min(dp[j], dp[j- i*i]+1); } } return dp[n]; } }
139 单词拆分
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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 <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串 互不相同
思路
二刷fail
因为题目中混合字符串， 所以一时没有想出来字符串的拆分和dp[]数组怎么建立联系， 如何知道s中是否含有wordDict的内容， 刚开始想到的是用集合来contains判断， 但是这样会导致时间复杂度极高， 比暴力还爆力，根本不可行，所以就没有ac下来。
先不考虑如何判断s中是否存在wordDict中的词， 先按照动态规划的思路将这道题理顺。
既然是看 wordDict是否在s中， 那么就把s看作背包， 看wordDict中的内容能否将其装满， 能那就返回true ，不能就是false ，暂时就这么简单的思考。
接下来按照动规五部曲。 dp[i] ：字符串长度为i， dp[i] = true，表示可以拆分为一个或多个在字典中出现的单词。
初始化dp[0] = true 。因为dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。
实现
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 str: wordDict){ int len = str.length(); //判断是否满足条件 //1. len<=i //2. s.substring(i-len, i) == str //3. dp的递推公式中的dp[i-len] == true ，需要判断上一个循环是否满足条件 if(i>= len && dp[i-len] && str.equals(s.substring(i-len,i))){ dp[i] = true; break; } } } return dp[s.length()]; } }
