视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh

https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html

1.本题对于dp数组的含义的确定非常重要，dp[i]表示前i个字符在给定数组内是否能找得到，s = "applepenapple", wordDict = ["apple", "pen"]像是这样的数据，我们需要[0,1,0]的方法而不是[0,0,1]的方法虽然都能组成对应的结果但是要有序，所以是排列的形式，还是先遍历背包后遍历物品，而且我觉得在题中应该一直记得自己的dp数组的含义，像是本题，我只一直疑惑的是第一层循环为什么可以是i <= s.size()我觉得会下标越界，但是本题的dp数组的含义是前i个字符是否符合要求，所以不是遍历s这个数组。

CPP

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