139、單詞拆分：

class Solution(object):def wordBreak(self, s, wordDict):""":type s: str:type wordDict: List[str]:rtype: bool"""n = len(s)dp = [False] * (n + 1)dp[0] = Truemap_word = set(wordDict)for j in range(1, n + 1):for i in range(j):if dp[i] == True and s[i:j] in map_word:dp[j] = Truereturn dp[n]

本題狀態轉移方程需要遍歷字符串，根據字符i和j之間的子字符串是否出現在字典中，來判斷dp[j]的狀態，感覺上確實不像是背包問題，沒必要硬套

背包問題總結：

01背包和完全背包：

01背包的二維dp數組實現先遍歷物品或背包都行，第二層循環遍歷是從小到大；而一維dp數組實現是先遍歷物品，后遍歷背包，且背包遍歷是從大到小；

完全背包問題要根據題目判斷是組合還是排列問題，求組合數是先物品后背包，求排列數是先背包后物品，兩層循環遍歷均是從小到大。