1?139. 單詞拆分

139.?單詞拆分

做了很久...估計2h 一開始我的思路卡死了?+ 看題解之后的思路的詳解見注釋，

我的寫法和carl 答案在一些微小的細(xì)節(jié)上略有不同，我的更好理解，但他的解法更簡單。

我寫的過程中，需要注意下標(biāo)和字符串大小的關(guān)系要不要+1-1，而且dp[] 需要從1開始到n有意義，dp[0] 不管它。不可以只有0,...,n-1 這樣會忽略s = "a" Dict = ["b"] 這樣的樣例，因為dp[0] 恒為1。

AC代碼：

class Solution {
public://多重背包且排列/*一開始我的思路——物品:字典里面str背包:容量為？的背包  求裝滿時候的情況dp[wordDict.size()][s.size()]如果n = wordDict.size() m = s.size()  又感覺要考慮每個字符和Dict中每個字符串的關(guān)系 很麻煩        *//*看了題解，才知道我糾結(jié)的地方 每個字符和Dict中每個字符串的關(guān)系 很麻煩，但其實可以用substr函數(shù)考慮背包的s的子串和Dict中每個字符串來比較，這樣就變得很簡單了。而且之前思考時候不知道dp[]存的值要是int還是char什么東西其實就題目結(jié)果反推，dp[] = trur/flase*/bool dp[310];   //以i結(jié)尾的字符串是否可以利用字典中出現(xiàn)的單詞拼接出來/*dp[j] = dp[j - wordDict[i].size()] && substr(s,j - wordDict[i].size(),wordDict[i].size()) == wordDict[i];dp[0] = 1;多重背包+排列背包j++ 物體i++模擬——6 7 8 9 10 11j = 11 size = 5 dp[6]*/bool wordBreak(string s, vector<string>& wordDict) {dp[0] = 1;bool tmp[100][100];for(int j = 0; j <= s.size();j++){for(int i = 0; i　< wordDict.size();i++){if(j == wordDict[i].size())  // 能裝下一個dp[j] =  (s.substr(j  - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];else if(j > wordDict[i].size() )    // 能至少裝2個 dp[j] = dp[j  - wordDict[i].size()] && (s.substr(j - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];}}// for(int i = 0; i　< wordDict.size();i++)// {//     for(int j = 0; j < s.size();j++)//         cout << tmp[i][j] << ' ';//     cout << endl;// }return dp[s.size() ];}
};

2 多重背包

感覺考的不多，算法筆記也沒有，看看理論。

有N種物品和一個容量為V 的背包。第i種物品最多有Mi件可用，每件耗費(fèi)的空間是Ci ，價值是Wi 。求解將哪些物品裝入背包可使這些物品的耗費(fèi)的空間 總和不超過背包容量，且價值總和最大。

解法1：每件物品最多有Mi件可用，把Mi件攤開，其實就是一個01背包問題了。

解法2：解法1上優(yōu)化（神奇優(yōu)化方式–二進(jìn)制+拆包（具體過程見筆記本））

3 背包總結(jié)

from