题目链接：139. 单词拆分 - 力扣（LeetCode）

看能不能用字符串列表里面的字符串组成这个字符串，可以反复使用

即完全背包问题，同之前的完全平方数、零钱兑换，相当于给定几个数，可以反复用，看能不能组成某个数

定义dp[i]是目标字符串中以i为结尾的子串能不能由某个字符串word组成，如果可以，问题变成dp[i-word.size()]

此处组合需要考虑顺序，target遍历外层循环 

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