# 139.单词拆分

## 问题描述
[139.单词拆分](https://leetcode.cn/problems/word-break/)

## 解题思路
首先确定`dp`数组的含义，`dp[i] = 1`应该表示长度为`i`的字符串，可以拆分成字典中出现的单词;

则，`dp`的递推公式为:`dp[j] = dp[i] && [i, j]区间的字串可以拆分成字典中的单词`

初始化`dp`数组:`dp[0] = 1`。

这里要注意，先遍历体积，再遍历物品；如果倒过来，是不方便判断字串是否可以拆分的。

## 代码
```cpp
#include <string>
#include <unordered_set>
#include <vector>
using std::string;
using std::unordered_set;
using std::vector;
class Solution {
  public:
    bool wordBreak(string s, vector<string> &wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> dp(s.length() + 1, 0); // 0 为false
        dp[0] = 1;
        // 先遍历体积，再遍历物品
        for (int j = 0; j <= s.length(); j++) {
            for (int i = 0; i <= j; i++) {
                string word = s.substr(i, j - i);
                if (wordSet.find(word) != wordSet.end() && dp[i])
                    dp[j] = 1;
            }
        }
        return dp[s.size()];
    }
};
```