139. 单词拆分

思路
完全背包（一个物品可以选多次）
dp代表字符长度（容量）
初始化：
wordDict转为集合:集合in时间复杂度o(1)
dp初始为False dp[o]为空串的情况 默认True
i既可以理解成：i之前的总字符是否由字典里的单词拼接而成 以及[i:j]区间的开始字符
dp[i]==True and s[i:j] in wordDict: i之前的字符组成情况及i-j之间的字符情况：可以理解为 [0,j]（包含j）是根据[0,i]和[i:j]来决定，如果两个都是由字典组成，那[0,j]自然也是由字典组成，即d[j]=True (可以想象成d[i]=d[i-1]+X)

class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""#集合in时间复杂度o(1)wordDict=set(wordDict)#dp代表字符串长度dp=[False]*(len(s)+1)dp[0]=Truefor i in range(len(s)):for j in range(i+1,len(s)+1):if dp[i]==True and s[i:j] in wordDict:dp[j]=Truereturn dp[-1]