单词拆分

https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-interview-150

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(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break

        return dp[n]

我发现本质就是如果前j个可以拼出来，j~i也可以拼出来，那么前i个就都可以拼出来。到了第n个就做完了。