力扣-动态规划-139 单词拆分

思路

1. dp数组定义：用wordDict数组可以完成不超过j的字符串的可能为dp[j]
2. 递推公式：

   tmp = s.substr(j - wordDict[i].size(), wordDict[i].size());
   dp[j] = (dp[j - wordDict[i].size()] && wordDict[i] == tmp) || dp[j];

3. dp数组初始化：dp[0] = true;
4. 遍历顺序：由于算是排列问题，不同字典语句先后会影响判断，所以先遍历背包再遍历物品，当前容量在前一个容量完成了对所有物品遍历一遍
5. 时间复杂度：     

代码

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int j = 1; j <= s.size(); j++) {for (int i = 0; i < wordDict.size(); i++) {if (j >= wordDict[i].size()) {string tmp;tmp = s.substr(j - wordDict[i].size(), wordDict[i].size());dp[j] = (dp[j - wordDict[i].size()] && wordDict[i] == tmp) || dp[j];}}}return dp[s.size()];}
};