1、零钱兑换II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

感悟：总结一个递推公式，完全背包求解背包获得最大价值的递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])，而装满背包的递推公式为：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]。

class Solution {public int change(int amount, int[] coins) {if(coins.length == 0) return 0;int len = coins.length;int[][] dp = new int[len][amount+1];for(int j=coins[0];j<=amount;j++){if(j%coins[0] == 0) dp[0][j] = 1;}for(int i=0;i<len;i++){dp[i][0] = 1;}for(int i=1;i<len;i++){for(int j=0;j<=amount;j++){if(j < coins[i]){dp[i][j] = dp[i-1][j];}else{dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];}}}return dp[len-1][amount];}
}

2、组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

感悟：本题的特殊之处在于，顺序不同的序列当做不同的组合，对于这种强调顺序的情况，适用于用一维动态数组，遍历顺序需要有不一样的调整。如果求组合数就是外层for循环遍历物品，内层for遍历背包。如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {public int combinationSum4(int[] nums, int target) {int len = nums.length;if(len == 0) return 0;int[] dp = new int[target+1];dp[0] =1;for(int j=0;j<=target;j++){for(int i=0;i<len;i++){if(j >= nums[i]) {dp[j] += dp[j-nums[i]];}}}return dp[target];}
}

3、零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

感悟：典型的完全背包问题，dp[i]定义为凑成金额i时，所需要的最少硬币的个数，递推公式为：dp[i] = min(dp[i],dp[i-coins[j]]+1)，为了满足求最少的要求，需要初始化为dp数组为一个大的值

class Solution {public int coinChange(int[] coins, int amount) {int max = Integer.MAX_VALUE;int[] dp = new int[amount+1];for(int i=0;i<amount+1;i++){dp[i] = max;}dp[0] = 0;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 dp[amount] == max ? -1 : dp[amount];}
}

4、完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是

感悟：背包为n，物品为完全平方数，完全平方数为每个整数平方所得。这样和上题很类似。

class Solution {public int numSquares(int n) {int max = Integer.MAX_VALUE;int[] dp = new int[n+1];for(int i=0;i<n+1;i++){dp[i] = max;}dp[0] = 0;for(int i=1;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];}
}

5、单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

感悟：字符串顺序是固定的，所以这是一个排列问题，遍历顺序需要先遍历背包（这里的字符串s）再遍历物品（字符串列表）。

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 len = word.length();if(i>=len && dp[i-len] && s.substring(i-len,i).equals(word)){dp[i] = true;break;}}}return dp[s.length()];}
}