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()];}
}