题目：
Given a non-empty string s and a dictionary wordDict containing a list of non-emptywords, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because"leetcode"can be segmented as"leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because"applepenapple"can be segmented as"apple pen apple".
Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false
分析：
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
如果使用搜索的话应该是会超时的，这里使用动态规划的方法。
dp[i]表示字符串s的前i个字符能否被拆分，使用substr来截取字符串。
| l | e | e | t | c | o | d | e | ||
| dp | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | ? |
假如我们现在判断dp[i]的值，我们要同时判断dp[j]==1和后面的字符串(substr(j, i-j))是否在字典中是不是同时成立的。
比如现在要求dp[8]的值，j=0时，dp[0]==1但substr(0, 8-0)也就是leetcode不在字典中，当j=4时，dp[4]==1且substr(4, 8-4)也就是code在字典中，所以dp[8]赋值1。最后返回dp中最后的值即可。
| l | e | e | t | c | o | d | e | ||
| dp | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
注：在dp的长度要比字符串长度多1，是为了方便计算。
程序：
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> set_s(wordDict.begin(), wordDict.end());
vector<int> dp(s.size()+, );
dp[] = ;
for(int i = ; i < dp.size(); ++i){
for(int j = ; j <= i; ++j){
string it = s.substr(j, i-j);
if(set_s.count(it) && dp[j]){
dp[i] = ;
break;
}
}
}
if(dp.back()) return true;
else return false;
}
};