代码随想录算法训练营第四十五天| 139.单词拆分
文档讲解：代码随想录
视频讲解：代码随想录B站账号
状态：看了视频题解和文章解析后做出来了
139.单词拆分
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False] * (n+1)
dp[0] = True
max_len = max(map(len, wordDict))
for i in range(1, n+1):
for j in range(i-1, max(i - max_len - 1, -1), -1):
if dp[j] and s[j:i] in wordDict:
dp[i] = True
return dp[n]- 时间复杂度：O(n^2)
- 空间复杂度：O(n)
1. 确定dp数组以及下标的含义
dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
2. 确定递推公式
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
3. dp数组的初始化
从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。
4. 遍历顺序
这道题其实求的是排列，只有所有排列的方式都遍历一边，才能确定wordict能否组成目标字符串。
所以先遍历背包再遍历物品，从前往后遍历。
5. dp数组举例
