力扣链接：139.单词拆分

难度：⭐⭐

解题关键词：动态规划、背包问题

解题思路：动态规划 dp[i] = str.slice(j, i)在字典 && dp[j]

function wordBreak(s: string, wordDict: string[]): boolean {
  const len = s.length;
  const dict = new Set(wordDict);

  const dp = new Array(len + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= len; i++) {
    for (let j = 0; j < i; j++) {
      // 判断从 j 到 i 是在字典中的，并且前 j 个也可以满足
      if (dict.has(s.slice(j, i)) && dp[j]) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[len];
}