1.题目

2.思路

为啥说是完全背包呢：
单词=物品，字符串=背包，而单词能否组成字符串s，就是背包能否装满物品；并且是可以重复使用字典中的单词，即背包中可以重复使用。

（1）确定状态
$dp[i]$为true时表示前i的（字符串长度为i）可以拆分为一个或多个正常单词（字典里能找得到的），即字符串s的前i位能用wordDict中的单词表示。

（2）转移方程
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

（3）初始状态 + 边界情况
$dp[0]$为True表示空字符，满足条件。

（4）遍历顺序
i从0到n，j从i+1到n+1（注意下标为0处没放字符串）。

3.代码（python）

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:n = len(s)dp = [False] * (n + 1)dp[0] = True # 空字符串for i in range(n):for j in range(i + 1, n + 1):if(dp[i] and (s[i:j] in wordDict)):dp[j] = Truereturn dp[-1]