1 动态规划（完全背包）
基于问题本身，先背包后物品的顺序比较方便，也好理解
代码语言：javascript复制class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int bagSize = s.size();
vector<bool> dp(bagSize 1, false);
dp[0] = true;
for (int j = 1; j <= bagSize; j ) // 背包容量
for (int i = 0; i < wordDict.size(); i ) { // 物品
int dictLen = wordDict[i].size();
if (j >= dictLen && wordDict[i] == s.substr(j - dictLen, dictLen))
dp[j] = dp[j] || dp[j - dictLen];
}
return dp[bagSize];
}
};
