动态规划25：139. 单词拆分

解题步骤：

1.确定状态表示：dp[i]是什么

2.确定：dp[i]等于什么

3.：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        //dp[i]表示字符串s中[0,i]区间的字符串是否能被字典中的单词拼接而成
        //dp[i]=dp[j-1]&&check(s[j,i])
        //解释：将字符串s中[0,i]区间的字符串划分成[0,j-1]区间的字符串和[j,s]区间的单词
        //如果[0,j-1]区间的字符串能被字典中的单词拼接而成并且[j,s]区间的单词在字典中
        //则字符串s中[0,i]区间的字符串能被字典中的单词拼接而成
        //j是动态的，范围是0~s
        
        unordered_set<string> hash;
        for(auto& s:wordDict) hash.insert(s);

        size_t n=s.size();
        //创建dp表
        vector<bool> dp(n+1);//多开一个空间，简易初始化
        //初始化
        dp[0]=true;
        s=' '+s;//使原始字符的下标统一+1
        //填表
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=i;++j)
            {
                if(dp[j-1]&&hash.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }

            }
        }
        return dp[n];
    }
};