day51 动态规划part8 代码随想录算法训练营 139. 单词拆分

题目：139. 单词拆分

我的感悟：

• 背包最后一part，不错！！
• 这题不好，不写了。

理解难点：

• 状态转移方程如何写

听课笔记：

首次代码及思考过程：

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 可以用多次-->完全背包
        # 物品是worDict集合
        # 背包是s(目标)
        # 如果初始化?递推公式是什么?
        # dp[j] += dp

看了别人的题解，比卡尔给的简洁

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]=True
        return dp[-1]

作者：吴彦祖
链接：https://leetcode.cn/problems/word-break/solutions/50986/dong-tai-gui-hua-ji-yi-hua-hui-su-zhu-xing-jie-shi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

通过截图：

•  自己没写，下回吧

扩展写法-回溯记忆化搜索：

import functools

class Solution:
    def __init__(self):
        self.wordSet = None

    @functools.lru_cache(None)# 改成这个更轻量级@functools.cache
    def backtracking(self, s: str, startIndex: int) -> bool:
        if startIndex >= len(s):
            return True

        for i in range(startIndex, len(s)):
            word = s[startIndex:i + 1]
            if word in self.wordSet and self.backtracking(s, i + 1):
                return True

        return False

    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        self.wordSet = set(wordDict)  # 将单词集合设置为实例变量
        return self.backtracking(s, 0)

资料：

139.单词拆分 

视频讲解：https://www.bilibili.com/video/BV1pd4y147Rh

https://programmercarl.com/0139.%E5%8D%95%E8%AF%8D%E6%8B%86%E5%88%86.html