力扣HOT100之动态规划：139. 单词拆分

这道题之前刷代码随想录的时候已经做过了，但是现在再做一遍还是不会，直接去看视频了。感觉这道题的dp数组很难想到，感觉做不出来也是情有可原吧。这道题目也是一个完全背包问题，字典里的单词就相当于物品，而字符串相当于背包，这道题可以理解为：能否用现有的物品恰好装满整个背包？接下来直接写动规五部曲：

1.确定dp[i]的含义：在字符串的长度为i的情况下，该字符串能否用字典中的单词拼接出来

2.确定递推公式 dp[i] = dp[j, i] is in wordDict && dp[j] == true

3.dp数组初始化 dp[0] = true （无意义，只是为了递推正常进行下去）

4.确定遍历顺序：先背包，再物品（涉及排列）

5.打印数组(省略)

首先dp数组的意义就很有意思：我们逐步增加字符串的长度（背包容量），直至恢复字符串本来的长度，然后我们在逐渐增加字符串长度的过程中不停地判断当前字符串能否被字典里的单词组成，很显然，假设字符串能够被字典中的单词组成，我们就一定可以在字符串长度增加到一定程度时，发现其正好与字典中的某个单词完全相等，我们将该长度时对应的dp数组位置设置为true，然后再进一步增加字符串的长度。我们可以想象：当字符串长度为i时，前面的某一节s[0] ~ s[j - 1]可以与字典内的单词完全匹配，我们只需要判断s[j] ~s[i]这一段能否与字典中的单词匹配即可，如果能找到这样一个j，使得dp[j] == true且s[j] ~s[i]这一段也能在字典中找到时，则说明字符串长度为i时，可以用字典中的单词组成，当逐渐将单词的长度扩大到原有的长度时，我们只需要判断dp[s.size()]是否为true即可。

class Solution {
public:
    bool wordBreak(string s, vector& wordDict) {
        //1.确定dp[i]的含义：在字符串的长度为i的情况下，该字符串能否用字典中的单词拼接出来
        //2.确定递推公式  dp[i] = dp[j, i] is in wordDict && dp[j] == true
        //3.dp数组初始化 dp[0] = true   //无意义，只是为了递推正常进行下去
        //4.确定遍历顺序：先背包，再物品（涉及排列）
        //5.打印数组(省略)
        int m = s.size();
        vector dp(m + 1, false);
        //初始化
        dp[0] = true;
        for(int i = 1; i   //遍历背包
            for(int j = 0; j