代码随想录算法训练营第三十八天-动态规划-完全背包-139.单词拆分

• 类似于回溯算法中的拆分回文串
• 题目是要求拆分字符串，问这些字符串是否出现在字典里。但这道题可以反着来考虑，从字典中的单词能不能组成所给定的字符串
  • 如果这样考虑， 这个字符串就背包，容器
  • 字典中的单词就是一个一个物品
  • 问题就转化成这些物品能不能正好装满这个背包，而且这些物品可以使用多次
  • 因此这是一个完全背包类问题
• 动规五部曲
  • dp[j]数组含义：把题目给定的字符串能不能用字典字符串来添满。字符串长度为j时，能被字典字符串来组成，就返回true，否则为false
  • 递推公式：道德字符串中[i, j]内容正好字典中，而且dp[i]也为true的话，dp[j]也就是true
  • 初始化值：dp[0]必须为true，否则递推出来的内容都会是false
    • 非0下标都要初始化为false
  • 遍历顺序：给定字符串的内容是确定的，也就是说字典中内容是一种排列效果来生成字符串，而不是组合出多种效果来组成字符串（也根本组不成）
    • 所以要先遍历背包，再遍历物品

class Solution {
public:
    bool wordBreak(std::string s, std::vector<std::string>& wordDict) {
        std::unordered_set<std::string> wordSet(wordDict.begin(), wordDict.end());
        std::vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                std::string word = s.substr(j, i - j);
                if (wordSet.find(word) != wordSet.end() && dp[j])
                    dp[i] = true;
            }
        }
        return dp.at(s.size());
    }
};

• 汇总