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 <= 2001 <= nums[i] <= 1000nums中的所有元素 互不相同1 <= target <= 1000
进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
题目中说到：从 nums 中找出并返回总和为 target 的元素组合的个数。 但是后面又紧跟着说顺序不同的作为不同的组合。 那么本题就不能看成单纯的组合数 ，而是排列。因为排列对于顺序有要求， 所以需要按照排列的思维去思考同时还需要有动态规划的思考。 这就是这道题难的地方。
按照动规的思路dp[i] : 表示总和为i的组合的个数为dp[i]
还有需要注意的就是遍历的顺序， 一般来说对于背包问题：
**求组合是外层遍历物品，内层遍历背包。 **
求排列是外层遍历背包，内层遍历物品。
所以，本题我们也是采用这种遍历方式进行。
实现
代码语言：javascript复制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 <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
思路
本题和我们之前做的零钱总换(地址: https://wclspace.xyz/post/4ee41ff3.html#518-零钱总换)是一个类型的题， 上一道这个题是要求返回凑成总金额的组合数， 而本题是返回可以凑成总金额所需的最少的硬币个数 所以这两道题在递推公式上略有不同。
dp[i]:表示 可以凑成总金额 i 所需的 最少的硬币个数为dp[i]
这道题对于遍历的位次顺序要求就没那么高了， 先遍历背包或者物品都行 ，这里我用先遍历物品（习惯）。同时， 因为对于数组中的银币的数量是无限制的， 所以我们可以一直使用同一个， 所以在内层遍历背包的时候需要正序遍历， 这样就可以保证同一个硬币被多次使用了。
注意： 因为要获取最少的硬币个数 ，所以在初始化dp数组的时候需要将其赋予最大值， 这样才能再每次递推的时候获取最小值（也就是最少使用硬币个数）
对于dp[0]的初始化，这里给dp[0] = 0，按照题意总金额为 0的个数也是 0 。 所以可以赋值为0 ， 至于其他的， 我们需要赋值为最大值 ，原因上面有说
实现
代码语言：javascript复制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， 否则就进行递推公式
代码语言：javascript复制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
实现
代码语言：javascript复制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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和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了。
实现
代码语言：javascript复制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()];
}
}
