如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。

如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

1.零錢兌換

題目

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

思路&代碼

1.dp數組與下標含義

dp[j]代表湊足總額為j的最少錢幣個數為dp[j]

2.遞推公式

小難

湊足總額為j - coins[i]的最少個數為dp[j - coins[i]]，那么只需要加上一個錢幣coins[i]即dp[j - coins[i]] + 1就是dp[j]（考慮coins[i]）

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

遞推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp數組初始化

因為取得是最小的，所以為了防止覆蓋，初始化就要初始化最大值

vector<int>dp(n+1,INT_MAX),

湊足總金額為0的錢幣個數也為0，dp[0]=0;

4.遍歷順序

要的是錢幣個數，無所謂排列組合，所以物品背包順序無所謂，注意for循環里的參數。

代碼

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int>dp(amount+1,INT_MAX);dp[0]=0;for(int i=0;i<coins.size();i++){for(int j=coins[i];j<=amount;j++){if(dp[j-coins[i]]!=INT_MAX){dp[j]=min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount]==INT_MAX) return -1;return dp[amount];}
};

2.完全平方數

說是跟上一題差不多，確實差不多（看了題解）

題目

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

代碼

class Solution {
public:int numSquares(int n) {//dp[j]代表實現j這個數的最小完全平方數數量//dp[j]=min(dp[j],dp[j-i*i]+1)vector<int>dp(n+1,INT_MAX);dp[0]=0;for(int i=1;i*i<=n;i++){for(int j=i*i;j<=n;j++){dp[j]=min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};

3.單詞拆分

有難度，沒太清楚

題目

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 <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s?和?wordDict[i]?僅由小寫英文字母組成
• wordDict?中的所有字符串?互不相同

代碼

1. 確定dp數組以及下標的含義

dp[i] : 字符串長度為i的話，dp[i]為true，表示可以拆分為一個或多個在字典中出現的單詞。

1. 確定遞推公式

如果確定dp[j] 是true，且 [j, i] 這個區間的子串出現在字典里，那么dp[i]一定是true。（j < i ）。

所以遞推公式是 if([j, i] 這個區間的子串出現在字典里 && dp[j]是true) 那么 dp[i] = true。

1. dp數組如何初始化

從遞推公式中可以看出，dp[i] 的狀態依靠 dp[j]是否為true，那么dp[0]就是遞推的根基，dp[0]一定要為true，否則遞推下去后面都都是false了。

那么dp[0]有沒有意義呢？

dp[0]表示如果字符串為空的話，說明出現在字典里。

但題目中說了“給定一個非空字符串 s” 所以測試數據中不會出現i為0的情況，那么dp[0]初始為true完全就是為了推導公式。

下標非0的dp[i]初始化為false，只要沒有被覆蓋說明都是不可拆分為一個或多個在字典中出現的單詞。

1. 確定遍歷順序

題目中說是拆分為一個或多個在字典中出現的單詞，所以這是完全背包。

還要討論兩層for循環的前后順序。

如果求組合數就是外層for循環遍歷物品，內層for遍歷背包。

如果求排列數就是外層for遍歷背包，內層for循環遍歷物品。

我在這里做一個總結：

求組合數：動態規劃：518.零錢兌換II?(opens new window)求排列數：動態規劃：377. 組合總和 Ⅳ?(opens new window)、動態規劃：70. 爬樓梯進階版（完全背包）?(opens new window)求最小數：動態規劃：322. 零錢兌換?(opens new window)、動態規劃：279.完全平方數(opens new window)

而本題其實我們求的是排列數，為什么呢。 拿 s = "applepenapple", wordDict = ["apple", "pen"] 舉例。

"apple", "pen" 是物品，那么我們要求 物品的組合一定是 "apple" + "pen" + "apple" 才能組成 "applepenapple"。

"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我們就是強調物品之間順序。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string>wordSet(wordDict.begin(),wordDict.end());vector<int>dp(s.size()+1,false);dp[0]=true;for(int i=1;i<=s.size();i++){ //背包for(int j=0;j<i;j++){ //物品string word=s.substr(j,i-j);if(wordSet.find(word)!=wordSet.end()&&dp[j]){dp[i]=true;}}}return dp[s.size()];}
};