32. Longest Valid Parentheses
dp[i] = dp[start - 1] + (i - start + 1): dp[i]表示到第i個(gè)位置為止的有效括號(hào)長(zhǎng)度躁倒，dp[start - 1]表示在start之前的有效括號(hào)長(zhǎng)度冰寻，i - start + 1表示從i到start中間的有效括號(hào)長(zhǎng)度艘刚，start是從棧里pop出來(lái)與右括號(hào)相對(duì)應(yīng)的左括號(hào)尔当，i是當(dāng)前右括號(hào)的下標(biāo)
if s[i] == '(': stack.append(i)，注意存放的是左括號(hào)下標(biāo)
else: if stack: start = stack.pop() 如果遇到了右括號(hào)，且棧不為空，就從stack里pop出一個(gè)左括號(hào)的下標(biāo)作為start
注意最后返回的是max(dp)
53. Maximum Subarray
假設(shè)我們已知第i步的global[i]（全局最優(yōu)）和local[i]（局部最優(yōu)），那么第i+1步的表達(dá)式是：
local[i+1]=Math.max(A[i], local[i]+A[i])馅扣，就是局部最優(yōu)是一定要包含當(dāng)前元素，所以不然就是上一步的局部最優(yōu)local[i]+當(dāng)前元素A[i]（因?yàn)閘ocal[i]一定包含第i個(gè)元素着降，所以不違反條件）差油，但是如果local[i]是負(fù)的，那么加上他就不如不需要的任洞，所以不然就是直接用A[i]蓄喇；
global[i+1]=Math(local[i+1],global[i])，有了當(dāng)前一步的局部最優(yōu)交掏，那么全局最優(yōu)就是當(dāng)前的局部最優(yōu)或者還是原來(lái)的全局最優(yōu)（所有情況都會(huì)被涵蓋進(jìn)來(lái)妆偏，因?yàn)樽顑?yōu)的解如果不包含當(dāng)前元素，那么前面會(huì)被維護(hù)在全局最優(yōu)里面盅弛，如果包含當(dāng)前元素钱骂，那么就是這個(gè)局部最優(yōu)）
70. Climbing Stairs
這道題目是求跑樓梯的可行解法數(shù)量叔锐。每一步可以爬一格或者兩個(gè)樓梯，可以發(fā)現(xiàn)见秽，遞推式是f(n)=f(n-1)+f(n-2)愉烙，也就是等于前一格的可行數(shù)量加上前兩格的可行數(shù)量。熟悉的朋友可能發(fā)現(xiàn)了解取，這個(gè)遞歸式正是[斐波那契數(shù)列]
注意當(dāng)n==0時(shí)步责，也返回1. 初始化時(shí)，dp[0]=1, dp[1] = 2禀苦， 是從0和1開(kāi)始蔓肯，不是從1和2開(kāi)始。
follow up是有沒(méi)有更好的解法： 有振乏，O(logn)省核，使用斐波那契的通項(xiàng)公式
91. Decode Ways
dp[i]存儲(chǔ)的是加入s中第i-1個(gè)元素后有多少種decode方式，所以dp[]初始化時(shí)的長(zhǎng)度要比s多一位昆码，并且使dp[0]=1
- 注意，0只能出現(xiàn)在1或者2后邊邻储，構(gòu)成10赋咽，20，如果單獨(dú)出現(xiàn)的0吨娜，則無(wú)法解析
- 如果字符s[i-1]不為0脓匿，則這個(gè)字符可以獨(dú)立地被解析，例如：1-9宦赠，
dp[i] += dp[i-1] - 如果字符s[i-2:i]大于'09'且小于'27'陪毡，證明i-1位字符和i-2位字符可以放在一起被解析，
dp[i] += dp[i-2] -
dp[i-2:i] < '27'這是按ASCII碼值來(lái)比較的勾扭，python中可以對(duì)字符串進(jìn)行比較毡琉，都是先將其轉(zhuǎn)換為ASCII碼值。其中妙色，大寫(xiě)字母的值都小于小寫(xiě)字母桅滋，同時(shí)（'ab'<'abc'）即空位的序數(shù)為所有字符最小 - 最后返回dp[-1]
96. Unique Binary Search Trees
這道題在樹(shù)的分類里已經(jīng)寫(xiě)過(guò)了，但還是有些細(xì)節(jié)需要添加身辨。
- res數(shù)組要初始化n+1位丐谋，因?yàn)榘?在內(nèi)了，并且res[0]和res[1]都要初始化為1煌珊，其余均為0
-
res[i]+= res[j]*res[i-j-1], res[j]代表i左邊的left branch數(shù)量号俐，res[i-j-1]代表right branch數(shù)量。j是i左邊的node個(gè)數(shù)定庵，i-j-1是i右邊的node個(gè)數(shù)吏饿，因?yàn)閚是順序分解的踪危，所以個(gè)數(shù)相同，生成的BST就相同找岖。 - 注意外層for循環(huán)i的范圍：
for i in range(2, n+1): - 最后返回res[n]
95. Unique Binary Search Trees II
雖然在dp分類里陨倡，但其實(shí)更偏向于divide and conquer
- 構(gòu)建一個(gè)生產(chǎn)子樹(shù)的函數(shù)，參數(shù)為start许布， end兴革，分別等于1和n
- 在這個(gè)函數(shù)內(nèi)，如果start>end蜜唾，就返回[None], 括號(hào)里一定要有none杂曲， 如果start==end, 就返回[TreeNode(start)]
-
for i in range(start, end+1)， end要加1 leftsubtree = self.generate(start, i-1), rightsubtree = self.generate(i+1, end)- 在for循環(huán)前要初始化
res = [] - 將左右子樹(shù)用兩個(gè)for循環(huán)排列組合起來(lái)袁余，要先
root = TreeNode(i), 每組合成功一個(gè)后就res.append(root)
120. Triangle
這道題之前也寫(xiě)過(guò)了擎勘，需要注意的點(diǎn)有：
- res初始化時(shí)的長(zhǎng)度為triangle最后一行的長(zhǎng)度再加1，加1是因?yàn)槿绻鹴riangle里只有一行颖榜，那就超出了遞歸式里的索引范圍
- 思路是將triangle reverse棚饵，然后針對(duì)每一行（倒序）里的每一個(gè)數(shù)字，更新res[i]掩完，等于當(dāng)前數(shù)字噪漾，加上一組的min(res[i], res[i+1])
- 最后返回res[0]， 因?yàn)榈谝恍兄挥幸粋€(gè)數(shù)字
121. Best Time to Buy and Sell Stock
又是局部最優(yōu)且蓬，全局最優(yōu)方法欣硼。初始化local和res均為0， 先判斷數(shù)組是不是遞減的恶阴，如果是就返回0if sorted(prices) == prices[::-1]: return 0
若不是遞減的诈胜，針對(duì)數(shù)組中每一個(gè)數(shù)字，計(jì)算
local = max(0, local + prices[i+1] - prices[i]), res = max(res, local)
- i的循環(huán)范圍是
for i in range(len(prices)-1), 因?yàn)楹筮呌衖+1 - 更新local時(shí)冯事，應(yīng)該加上原來(lái)的Local, 和0比較是因?yàn)閮r(jià)格有可能是負(fù)數(shù)焦匈。
- 為什么要加上原來(lái)的Local, 因?yàn)?，5昵仅，3括授，6， 1到6的距離是5岩饼，等于（5-1）+（3-5）+（6-3）
139. Word Break
針對(duì)動(dòng)態(tài)規(guī)劃的思路：
- 決定存儲(chǔ)什么歷史信息以及用什么數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)
- 遞推式荚虚，就是如何從存儲(chǔ)的歷史信息中得到當(dāng)前結(jié)果
- 初始值的設(shè)定
這道題，dp[i]表示的是在s中的前i-1個(gè)字符s[:i]是否存在wordDict里籍茧，初始化dp的長(zhǎng)度要是s的長(zhǎng)度加1版述，因?yàn)橐鎯?chǔ)dp[0]=True
雙重for循環(huán)，注意內(nèi)層循環(huán)時(shí)j的范圍是for j in range(i, len(s)):, 從i開(kāi)始到字符串結(jié)束寞冯。
判斷條件if dp[i] and s[i:j+1] in wordDict: dp[j+1] = True
dp[i]為真證明s的前i-1個(gè)字符存在里邊渴析，如果s[i:j+1]也存在晚伙，我們就更新dp[j+1]為真
最后返回dp[-1]，d[7] is True because there is "code" in the dictionary that ends at the 7th index of "leetcode" AND d[3] is True
152. Maximum Product Subarray
和maximum sum subarray類似俭茧，只不過(guò)這道題是求最大乘積咆疗。方法也是先初始化maxlocal和res, 但這道題要再加一個(gè)minlocal，因?yàn)閮蓚€(gè)很小的負(fù)數(shù)相乘之后可能會(huì)變成很大的整數(shù)母债。所以對(duì)nums進(jìn)行遍歷時(shí)午磁，遞推式里要再加一項(xiàng)對(duì)minlocal的更新。
并且要注意因?yàn)橐呀?jīng)初始化了maxlocal, minlocal, res = nums[0], nums[0], nums[0], 所以for循環(huán)要從1開(kāi)始毡们。
在每次循環(huán)過(guò)程中：
maxcopy = maxlocal
maxlocal = max(maxlocal*nums[i], nums[i], minlocal*nums[i])
minlocal = min(maxcopy*nums[i], nums[i], minlocal*nums[i])
res = max(maxlocal, res)
要先將maxlocal復(fù)制一下迅皇，作為計(jì)算minloca時(shí)使用
62. Unique Paths
具體思路參考第161頁(yè)https://www.dropbox.com/s/d839bnp9lcroxmq/Sample_Interview_Questions_Set_16.pdf?dl=0
- 需要注意的是，我們可以用二維數(shù)組代替一維數(shù)組衙熔。只需要對(duì)一維數(shù)組更新m次就可以登颓。因?yàn)樵诙S數(shù)組中，每個(gè)方格所擁有的路徑數(shù)等于上邊方格?左邊方格红氯。在一維數(shù)組中框咙，每次更新時(shí)，當(dāng)前方格就屬于上邊方格痢甘，所以只需要加上左邊方格就可扁耐。
- 還有一點(diǎn)需要注意，內(nèi)部循環(huán)從1開(kāi)始. 這是因?yàn)榈谝涣兄忻總€(gè)方格的路徑數(shù)始終都是1
for i in range(m):
for j in range(1, n)```
- 初始化res[0] = 1产阱，res的長(zhǎng)度要和n一樣！块仆！
#63. Unique Paths II
在上一題的基礎(chǔ)上增加了障礙构蹬，即有的方格為1時(shí)便不可通過(guò)』诰荩總體思想沒(méi)有變化庄敛，依然可以用一維數(shù)組代替二維數(shù)組。
- 這次內(nèi)部循環(huán)不能從1開(kāi)始科汗，因?yàn)榈谝涣械姆礁裰杏锌赡艽嬖谡系K藻烤，即值為1，所以每次循環(huán)都要做判斷：
if board[i][j] == 1:
res[j] = 0
elif j > 0:
res[j] += res[j-1]
- 依然需要初始化res[0] = 1头滔，res的長(zhǎng)度要和n一樣２劳ぁ！
#64. Minimum Path Sum
依然是從左上角到右下角坤检，求最短路徑和兴猩。同樣使用一維數(shù)組，因?yàn)榈谝恍械拿總€(gè)元素只能從左邊那個(gè)元素過(guò)來(lái)早歇，所以grid第一行對(duì)應(yīng)的一維數(shù)組：
for i in range(1, n):
res[i] = res[i-1] + grid[0][i]
然后對(duì)一維數(shù)組更新Ｇ阒ァ讨勤！m-1次：
for i in range(1, m):
for j in range(n):
if j == 0:
res[j] = res[j] + grid[i][0]
else:
res[j] = min(res[j-1], res[j]) + grid[i][j]
- 當(dāng)j==0時(shí)，證明我們?cè)诟碌谝涣谐苛恚谝涣械脑刂荒苡缮线叺脑剡^(guò)來(lái)潭千，所以是上邊元素的值加上當(dāng)前元素的值，res[j]就是上一行的第一列的元素借尿。
- 當(dāng)j!=0時(shí)刨晴，針對(duì)每個(gè)元素，它可以從上或左的元素得到垛玻，我們就在上和左元素中選一個(gè)最小值割捅，再加上當(dāng)前元素。上邊的元素就是res[j]（因?yàn)榇藭r(shí)還沒(méi)有更新res[j]）, 左邊的元素就是res[j-1]