【学会动态规划】单词拆分（24）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学会动态规划】单词拆分（24）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

题目链接：139. 单词拆分 - 力扣（LeetCode）

【学会动态规划】单词拆分（24）,学会动态规划,动态规划,算法

题目很好理解，就是给我们一个字典，

看是否能够用字典里的字符串拼接成他给的目标字符串 s。

2. 算法原理

1. 状态表示

dp[ i ] 表示的是从起点到 dp[ i ] 的字符串是否能被字典里的字符串拼接成，

如果成就是 true，否则就是 false

2. 状态转移方程

根据最后一个位置的情况来划分问题，

我们可以把它分成两个区间来分析，

左区间能否可以拼接成功？右区间是否是字典里的字符串？

所以我们的状态转移方程就是：

左区间 == true && 右区间存在字典中，否则就是 false

3. 初始化

为了防止越界加一个虚拟的头结点即可。

4. 填表顺序

从左往右。

5. 返回值

返回 dp 表的最后一个位置

3. 代码编写

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st;
        for(auto e : wordDict) st.insert(e);

        vector<bool> dp(s.size() + 1);
        dp[0] = true;
        for(int i = 0; i <= s.size(); i++) {
            for(int j = 0; j < i; j++) {
                if(dp[j] && st.find(s.substr(j, i - j)) != st.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.size()];
    }
};