101. Leetcode 139. 单词拆分 (动态规划-完全背包)

步骤一、确定状态:

确定dp数组及下标含义

dp[j]表示的是长度为j的字符串(容量为j的背包)能否被拆分成1个或者多个单词 里面的值， 所以这里的dp[j]非1即0

步骤二、推断状态方程:

if dp[i] and s[i:j] in wordDict: dp[j] = True

步骤三、规定初始条件:

初始条件:

首先全局初始化的话都是False， 只要没有被覆盖说明都是不可拆分为一个或多个在字典中 出现的单词。而dp[0]需要初始化True，这里为了往下递推，如果也是False的话，那就都 是False了。

步骤四、计算顺序:

对于背包， 依然是正向遍历，而对于物品，也是正向遍历，因为这里的物品 可以取多次

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:n = len(s)dp = [False for _ in range(n + 1)]dp[0] = Truefor 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]

 

总结

以上是生活随笔为你收集整理的101. Leetcode 139. 单词拆分 (动态规划-完全背包)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。