LC139單詞拆分(未掌握)

1. 未掌握分析：將字符串s中的各個字符看成是背包，思考成了多重背包問題
2. 單詞就是物品，字符串s就是背包，單詞能否組成字符串s，就是問物品能不能把背包裝滿。拆分時可以重復使用字典中的單詞，說明就是一個完全背包！只不過與一般的完全背包不同的是需要考慮物品的順序問題，物品并不能隨意擺放在背包中
3. dp數(shù)組的含義：dp[i] : 字符串長度為i的話，dp[i]為true，表示可以拆分為一個或多個在字典中出現(xiàn)的單詞
4. 確定遞推公式：如果確定dp[j] 是true，且 [j, i] 這個區(qū)間的子串出現(xiàn)在字典里，那么dp[i]一定是true。（j < i ）。
5. 由題意可知，物品的擺放有順序可言，因此是先遍歷背包再遍歷物品，是排列問題
6. 代碼
   

多重背包問題

1. 其實是和01背包一樣，只不過是加了一個數(shù)量數(shù)組，將i類的物品的數(shù)量j攤開來看成是j類物品即可
2. 多加一層循環(huán)用來復用j次i類物品
3. 先物品再背包，并且背包從大到小防止物品復用
4. 代碼