題目：279.完全平方數

本題比較簡單，幾天沒做背包但是這道題很快ac了

嘗試解答：

????????題目類型：給定一個背包容量，求裝滿背包的最少物品數，且每個物品可以放多次，完全背包

? ? ? ??1.dp[j]數組含義：裝滿容量為 j?的背包所需要的物品數為dp[j]?

? ? ? ? 2.狀態轉移方程：dp[j] = min(dp[j], dp[j - i * i] + 1)

? ? ? ? 3.初始化：dp[0] =??0（這個是通過測試集試出來的），0之外的位置初始化為最大值，防止將答案覆蓋

? ? ? ? 4.遍歷順序：必須先遍歷背包，在物品的終止條件中會用到背包容量作為限制。如果先遍歷物品，那不知道for在哪里終止。
? ? ? ? 5.打印dp

class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX);      //0之外的位置初始化為最大值，防止將答案覆蓋dp[0] = 0;for(int j = 0; j <= n; j++){     //先背包后物品for(int i = 1; i <= n && i * i <= j; i++){     //for循環的判斷條件里要多一條平方數小于背包容量，防止訪問越界dp[j] = min(dp[j], dp[j - i * i] + 1);    //統計方法數}}return dp[n];}
};

其實先遍歷物品后遍歷背包也可以，只不過要加上一個防止訪問越界的判斷條件if

題目：139.單詞拆分

嘗試：失敗

這道題相當于是判斷給定容量的背包能不能裝滿。背包總容量s.size()

這個背包的總容量為s.size()，如果到最后背包內所裝物品的數量為s.size()，就返回true，否則返回false.

1.dp[j]含義：容量為j的背包所裝物品的數目

2.動態轉移方程：如果字典里有[i]，dp[j] = dp[j - ] + 1;

3.初始化：dp[0] =?

4.遍歷順序：先后順序沒有影響，背包的順序從小到大

正解：

本題應該是求排列數類型

1.dp數組含義：字符串的長度為 i，能否能裝滿

2.遞推公式：截取[i , j]這一段的s，判斷這個子串是否存在于字典中，先將數組字典轉化為set,set中查詢的函數為find()。if([i，j] && dp[i] == true) 則 dp[j] == true; else dp[j] == false

3.初始化：dp[0] = true，非零下標都為false

4.遍歷順序：求排列數，先遍歷背包再物品

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for(int j = 0; j <= s.size(); j++){      //先背包for(int i = 0; i <= j; i++){string word = s.substr(i, j - i);     //將s進行剪切賦值給str//substr(起始位置，截取的個數)if(wordSet.find(word) != wordSet.end() && dp[i] == true){dp[j] = true;}}}return dp[s.size()];}
};

[易錯]：if的判斷條件里應該是dp[i] == true，因為要判斷的是i之前的字符串是否查詢成功了，不要慣性思維寫dp[j - i] == true。

[注意]：各種語法：比如轉字典、字典查詢、切割字符串等