【leetcode100-086到090】【动态规划】一维五题合集2

【单词���分】

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

思路：

首先，我们依次考虑s的前i个字母能否被分割，直到i=n；

对一个确定的i，我们尝试在前i个字母中进行分割，枚举每一个分割点，如果分割点前面的部分能分割（肯定已经被计算过，直接查表即可），且分割点后的部分存在于 wordDict中，那么当前子串就是可分割的，记录到表中；

最后检查dp[n]即可。

class Solution {public:    bool wordBreak(string s, vector& wordDict) {        int n = s.size();        // dp        vector dp(n + 1, false);        dp[0] = true;        //递推        for (int i = 1; i