動(dòng)態(tài)規(guī)劃如何測(cè)試是否超時(shí)？
動(dòng)態(tài)規(guī)劃法（dynamic programming）通常用于求解最優(yōu)化問(wèn)題（optimization problem），它適用于那些子問(wèn)題相互重疊的情況，即子問(wèn)題不獨(dú)立，不同的子問(wèn)題具有公共的子子問(wèn)題（就是子問(wèn)題的子問(wèn)題）。這顯然與分治法是不同的，分治法將問(wèn)題劃分為不重疊的子問(wèn)題，然后分別求解這些子問(wèn)題，最后將這些問(wèn)題合并得到最終的解。
對(duì)于具有公共子問(wèn)題的情況，分治法會(huì)做很多不必要的工作，它會(huì)多次求解同一子子問(wèn)題。動(dòng)態(tài)規(guī)劃法卻不一樣，對(duì)每個(gè)子子問(wèn)題它只會(huì)求解一次，將其保存在一個(gè)表格中，避免了不必要的重復(fù)計(jì)算。
利用動(dòng)態(tài)規(guī)劃法求出來(lái)的是這個(gè)問(wèn)題的一個(gè)最優(yōu)解（an optimal solution），記住這里求解的只是最優(yōu)解（the optimal solution）中的一個(gè)，因?yàn)樽顑?yōu)解可能有多個(gè)。
適用dp的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性。
1.最優(yōu)化原理：如果問(wèn)題的最優(yōu)解包含的子問(wèn)題的解也是最優(yōu)解，則稱該問(wèn)題具有最有子結(jié)構(gòu)，即滿足最優(yōu)化原理。（也即子結(jié)構(gòu)最優(yōu)時(shí)通過(guò)選擇后一定最優(yōu)）
2.無(wú)后效性：某階段的狀態(tài)一旦確定，則此后過(guò)程的演變不再受此前各種狀態(tài)及決策的影響，簡(jiǎn)單的說(shuō)，就是“未來(lái)與過(guò)去無(wú)關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響過(guò)程未來(lái)的演變。
3.重疊子問(wèn)題：即子問(wèn)題之間是不獨(dú)立的，一個(gè)子問(wèn)題在下一階段決策中可能被多次使用到。（該性質(zhì)并不是動(dòng)態(tài)規(guī)劃適用的必要條件，但是如果沒(méi)有這條性質(zhì)，動(dòng)態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢(shì)）。其實(shí)本質(zhì)上dp就是一個(gè)以空間換時(shí)間的做法，為了降低時(shí)間復(fù)雜度，不對(duì)子問(wèn)題進(jìn)行重復(fù)計(jì)算，其必須存儲(chǔ)過(guò)程中的各種狀態(tài)。
動(dòng)態(tài)規(guī)劃可以從暴力枚舉逐步優(yōu)化得到。問(wèn)題求解的各個(gè)方法:暴力枚舉->遞歸->備忘錄算法->動(dòng)歸算法
[leetcode]10.Regular Expression Matching
對(duì)于p字符串有點(diǎn)、字母、點(diǎn).
.
、字母?
?
四種元素，點(diǎn)匹配任意一個(gè)字母，字母匹配相同的一個(gè)字母，點(diǎn)?
?
匹配任意字母（可以是任意不同字母，例如.?
.
?
匹配abc），字母?
?
匹配連續(xù)任意個(gè)相同字母，值得注意的是?
?
的任意包括0個(gè)。由于?
?
可以匹配任意個(gè)，造成檢驗(yàn)s和p是否完全匹配的時(shí)候難以確定究竟?
?
匹配幾個(gè)字母合適，這正是本題的關(guān)鍵點(diǎn)。
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
# dynamic programming
len_s = len(s)
len_p = len(p)
# initialize
dp = [[False for i in range (len_p+1)] for j in range(len_s+1)]
dp[0][0] = True
# initialize dp[0][j]
for j in range(1,len_p):
if p[j] == '*':
dp[0][j+1] = dp [0][j-1]
for i in range(1,len_s+1):
for j in range(1,len_p+1):
if s[i-1] == p[j-1] or p[j-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = (dp[i-1][j-2] and (p[j-2] == s[i-1] or p[j-2] == '.')) or dp[i][j-2] or
(dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] =='.'))
return dp[len_s][len_p]
相似的題目還有：[leetcode]44.Wildcard Matching;
[leetcode]62.Unique Paths
動(dòng)態(tài)規(guī)劃的關(guān)鍵是要得到遞推關(guān)系式。對(duì)于本題，到達(dá)某一點(diǎn)的路徑數(shù)等于到達(dá)它上一點(diǎn)的路徑數(shù)與它左邊的路徑數(shù)之和。也即，起點(diǎn)到點(diǎn)(i, j)的路徑總數(shù)：ways[i][j] = 起點(diǎn)到點(diǎn)(i, j-1)的總數(shù)：ways[i][j-1] + 起點(diǎn)到點(diǎn)(i-1, j)總數(shù)：ways[i-1][j]。于是我們就得到遞推關(guān)系式：????[?][?]=????[?][??1]+????[??1][?]
w
a
y
s
[
i
]
[
j
]
=
w
a
y
s
[
i
]
[
j
?
1
]
+
w
a
y
s
[
i
?
1
]
[
j
]
class Solution:
def uniquePaths(self, m, n):
paths = [[1 for i in range(n)] for i in range(m)]
for i in range(1,m):
for j in range(1,n):
paths[i][j] = paths[i-1][j]+paths[i][j-1]
return paths[m - 1][n - 1]
相似的題目還有：[leetcode]63.Unique Paths II;[leetcode]64.Minimum Path Sum
[leetcode]72.Edit Distance
編輯距離也是一個(gè)極其重要和經(jīng)典的問(wèn)題了。
這個(gè)算法計(jì)算的是將s[1…i]轉(zhuǎn)換為t[1…j]（例如將kitten轉(zhuǎn)換為sitting）所需最少的操作數(shù)（也就是所謂的編輯距離），這個(gè)操作數(shù)被保存在d[i,j]（d代表的就是上圖所示的二維數(shù)組）中。
在第一行與第一列肯定是正確的，這也很好理解，例如我們將kitten轉(zhuǎn)換為空字符串，我們需要進(jìn)行的操作數(shù)為kitten的長(zhǎng)度（所進(jìn)行的操作為將kitten所有的字符丟棄）。
我們對(duì)字符可能進(jìn)行的操作有三種：
如果我們可以使用k個(gè)操作數(shù)把s[1…i]轉(zhuǎn)換為t[1…j-1]，我們只需要把t[j]加在最后面就能將s[1…i]轉(zhuǎn)換為t[1…j]，操作數(shù)為k+1
如果我們可以使用k個(gè)操作數(shù)把s[1…i-1]轉(zhuǎn)換為t[1…j]，我們只需要把s[i]從最后刪除就可以完成轉(zhuǎn)換，操作數(shù)為k+1
如果我們可以使用k個(gè)操作數(shù)把s[1…i-1]轉(zhuǎn)換為t[1…j-1]，我們只需要在需要的情況下（s[i] != t[j]）把s[i]替換為t[j]，所需的操作數(shù)為k+cost（cost代表是否需要轉(zhuǎn)換，如果s[i]==t[j]，則cost為0，否則為1）。
將s[1…n]轉(zhuǎn)換為t[1…m]當(dāng)然需要將所有的s轉(zhuǎn)換為所有的t，所以，d[n,m]（表格的右下角）就是我們所需的結(jié)果。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m,n = len(word1),len(word2)
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==j==0:
dp[0][0] = 0
elif i==0:
dp[0][j] = j
elif j==0:
dp[i][0] = i
else:
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1+min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
return dp[-1][-1]
[leetcode]91.Decode Ways
很顯然，由于本題只要求有多少種decode的方法，而不要求把每種方法都列出來(lái)，所以用DP。假設(shè)當(dāng)前的元素為Z，他前面的兩個(gè)為XY， i.e.XYZ。
1.如果Z=0, 并且Y=1 or 2。 那么對(duì)應(yīng)于Z的DP值等于X的DP值，因?yàn)閷?duì)于10只有一種解釋方式，所以 DP[i] = DP[i-2]。
2.如果 YZ 位于[11, 19] 或者 [21, 26] 這兩個(gè)range中，那么顯然對(duì)于這個(gè)兩位數(shù)我們有兩種decode的方式，也就是說(shuō) DP[i] = DP[i-1]+DP[i-2], 注意這里不是DP[i] = DP[i-1]+1。 例如 1212中的最后一個(gè)2。
3.如果X不是0， 例如YZ = 81。 那么DP[i] = DP[i-1].
最后注意的是由于2中我們要取到DP[i-2]，所以我們?cè)诔跏糄P list的時(shí)候在最前面加上一個(gè)1。由于加上了最前面的這個(gè)1。所以當(dāng)DP[i]對(duì)應(yīng)的是s[i-1]。 YZ對(duì)應(yīng)的就是 s[(i-1)-1:(i-1)+1]。
class Solution:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
dp = [1 for i in range(len(s)+1)]
for i in range(2,len(s)+1):
nums = s[i-2:i]
if 1<int(nums)<10 :
dp[i] = dp[i-1]
elif 11<=int(nums)<=19 or 21<=int(nums)<=26:
dp[i] = dp[i-1]+dp[i-2]
elif int(nums) == 10 or int(nums) == 20:
dp[i] = dp[i-2]
elif nums[-1]=='0':
dp[i] = 0
else:
dp[i] = dp[i-1]
return dp[-1]
[leetcode]97.Interleaving String
可以用遞歸做，每匹配s1或者s2中任意一個(gè)就遞歸下去。但是會(huì)超時(shí)。
因此考慮用動(dòng)態(tài)規(guī)劃做。
s1, s2只有兩個(gè)字符串，因此可以展平為一個(gè)二維地圖，判斷是否能從左上角走到右下角。
當(dāng)s1到達(dá)第i個(gè)元素，s2到達(dá)第j個(gè)元素:
地圖上往右一步就是s2[j-1]匹配s3[i+j-1]。
地圖上往下一步就是s1[i-1]匹配s3[i+j-1]。
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if not s1:return s2==s3
if not s2:return s1==s3
m,n = len(s1),len(s2)
if m+n != len(s3):return False
dp = [[False for j in range(n+1)] for i in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i==j==0:
dp[i][j] = True
elif i == 0:
dp[0][j] = (dp[0][j-1] and s2[j-1] == s3[j-1])
elif j == 0:
dp[i][0] = (dp[i-1][0] and s1[i-1] == s3[i-1])
else:
dp[i][j] = (dp[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] == s3[i+j-1])
return dp[m][n]
[leetcode]115.Distinct Subsequences
互異子序列。用dp[i][j]記錄S的前i個(gè)和T的前j個(gè)的符合個(gè)數(shù)，那么最后目標(biāo)就是dp[S.size()][T.size()];
初始化，j = 0 時(shí)候，dp[i][0] = 1，因?yàn)樗械亩伎梢酝ㄟ^(guò)刪除所有變成空字符，并且只有一種。
遞推式子如下了：
i和j都從1開(kāi)始，且j不能大于i，因?yàn)槠ヅ涞拈L(zhǎng)度至少為1開(kāi)始，j大于i無(wú)意義
如果 ?==?
i
==
j
那么 dp[i][j] = S.substr(0, i) == T.substr(0, j);
如果 ?!=?
i
!
=
j
分兩種情況
S[i-1] != T[j-1] 時(shí)，也就是加入不加入i的影響是一樣的，那么 dp[i][j] = dp[i - 1][j];
S[i-1] == T[j-1] 時(shí)，那么當(dāng)前字符可選擇匹配或者是不匹配，所以dp[i][j] = dp[i - 1][j -1] + dp[i - 1][j];
class Solution:
def numDistinct(self, s: str, t: str) -> int:
m,n = len(s),len(t)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
dp[0][0] = 1
for j in range(1,m+1):
dp[0][j] = 1
for i in range(1,n+1):
for j in range(1,m+1):
if t[i-1] == s[j-1]:
dp[i][j] = dp[i-1][j-1]+dp[i][j-1]
else:
dp[i][j] = dp[i][j-1]
return dp[n][m]
[leetcode]123.Best Time to Buy and Sell Stock III
這道是買股票的最佳時(shí)間系列問(wèn)題中最難最復(fù)雜的一道，前面兩道 Best Time to Buy and Sell Stock 和 Best Time to Buy and Sell Stock II 的思路都非常的簡(jiǎn)潔明了，算法也很簡(jiǎn)單。而這道是要求最多交易兩次，找到最大利潤(rùn)，還是需要用動(dòng)態(tài)規(guī)劃Dynamic Programming來(lái)解，而這里我們需要兩個(gè)遞推公式來(lái)分別更新兩個(gè)變量local和global.我們其實(shí)可以求至少k次交易的最大利潤(rùn)，找到通解后可以設(shè)定 k = 2，即為本題的解答。我們定義local[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易并且最后一次交易在最后一天賣出的最大利潤(rùn)，此為局部最優(yōu)。然后我們定義global[i][j]為在到達(dá)第i天時(shí)最多可進(jìn)行j次交易的最大利潤(rùn)，此為全局最優(yōu)。它們的遞推式為：
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])
其中局部最優(yōu)值是比較前一天并少交易一次的全局最優(yōu)加上大于0的差值，和前一天的局部最優(yōu)加上差值中取較大值，而全局最優(yōu)比較局部最優(yōu)和前一天的全局最優(yōu)，代碼如下：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
# 二維數(shù)組
# k = 2
# local = [[0 for j in range(k+1)] for i in range(len(prices))]
# glob = [[0 for j in range(k+1)] for i in range(len(prices))]
# for i in range(1,len(prices)):
# diff = prices[i]-prices[i-1]
# for j in range(1,k+1):
# local[i][j] = max(local[i-1][j]+diff,glob[i-1][j-1]+diff)
# glob[i][j] = max(glob[i-1][j],local[i][j])
# return glob[-1][-1]
# 一維數(shù)組
k = 2
local = [0 for j in range(k+1)]
glob = [0 for j in range(k+1)]
for i in range(1,len(prices)):
diff = prices[i]-prices[i-1]
for j in reversed(range(1,k+1)):
local[j] = max(local[j]+diff,glob[j-1]+diff)
glob[j] = max(glob[j],local[j])
return glob[-1]
其實(shí)可以總結(jié)為兩個(gè)狀態(tài)的DP，分別代表當(dāng)天必須賣的利潤(rùn)和不一定當(dāng)天賣的利潤(rùn)。
[leetcode]132.Palindrome Partitioning II
輸入一個(gè)字符串，將其進(jìn)行分割，分割后各個(gè)子串必須是“回文”結(jié)構(gòu)，要求最少的分割次數(shù)。顯然，為了求取最少分割次數(shù)，一個(gè)簡(jiǎn)單的思路是窮盡所有分割情況，再?gòu)闹姓页龇指詈罂蓸?gòu)成回文子串且次數(shù)最少的分割方法。
對(duì)于一個(gè)字符串，我們需要考慮所有可能的分割，這個(gè)問(wèn)題可以抽象成一個(gè)DP問(wèn)題，對(duì)于一個(gè)長(zhǎng)度為n的字符串，設(shè)DP[i][j]表示第i個(gè)字符到第j個(gè)字符是否構(gòu)成回文，若是，則DP[i][j]=1;若否，則DP[i][j]=0
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [(i-1) for i in range(n + 1)]
for i in range(n + 1):
for j in range(i):
tmp = s[j:i]
if tmp == tmp[::-1]:
dp[i] = min(dp[i], dp[j] + 1)
return dp[n]
[leetcode]139.Word Break
動(dòng)態(tài)規(guī)劃。dp[i]表示字符串s[:i]能否拆分成符合要求的子字符串。我們可以看出，如果s[j:i]在給定的字符串組中，且dp[j]為True（即字符串s[:j]能夠拆分成符合要求的子字符串），那么此時(shí)dp[i]也就為True了。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(len(s)+1):
for k in range(i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
# break
return dp[len(s)]
以上關(guān)于字符串的動(dòng)態(tài)規(guī)劃，我們可以發(fā)現(xiàn)：對(duì)于字符串求最長(zhǎng)/短，最大/小的最優(yōu)解，我們可以通過(guò)分析子問(wèn)題來(lái)分解問(wèn)題的求解，通過(guò)子問(wèn)題的求解來(lái)完成整體的最優(yōu)解。
[leetcode]174.Dungeon Game
自底向上的動(dòng)態(tài)規(guī)劃
在走完最后一個(gè)房間的時(shí)候血量至少要剩下１，因此最后的狀態(tài)可以當(dāng)成是初始狀態(tài)，由后往前依次決定在每一個(gè)位置至少要有多少血量, 這樣一個(gè)位置的狀態(tài)是由其下面一個(gè)和和左邊一個(gè)的較小狀態(tài)決定 ．因此一個(gè)基本的狀態(tài)方程是: dp[i][j] = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j].
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
m, n = len(dungeon), len(dungeon[0])
dp = [[0 for j in range(n)]for i in range(m)]
for i in reversed(range(m)):
for j in reversed(range(n)):
if i == m-1 and j == n-1:
dp[i][j] = max(0, -dungeon[i][j])
elif i == m-1:
dp[i][j] = max(0, dp[i][j+1] - dungeon[i][j])
elif j == n-1:
dp[i][j] = max(0, dp[i+1][j] - dungeon[i][j])
else:
dp[i][j] = max(0, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
return dp[0][0] + 1
[leetcode]198.House Robber
動(dòng)態(tài)規(guī)劃DP。本質(zhì)相當(dāng)于在一列數(shù)組中取出一個(gè)或多個(gè)不相鄰數(shù)，使其和最大。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:return 0
dp = [0 for i in range(len(nums)+1)]
for i in range(1,len(nums)+1):
if i==1:
dp[1] = nums[0]
else:
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[-1]
[leetcode]213.House Robber II
這個(gè)題多了環(huán)的條件，在這個(gè)約束下就多了個(gè)不同時(shí)偷第一個(gè)和最后一個(gè)就可以了。所以，兩種偷的情況：第一種不偷最后一個(gè)房間，第二種不偷第一個(gè)房間，求這兩種偷法能獲得的最大值。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:return 0
elif len(nums)==1:return nums[0]
elif len(nums)==2:return max(nums[0],nums[1])
else:
return max(self._rob(nums[1:]),self._rob(nums[:-1]))
def _rob(self,nums):
if not nums:return 0
dp = [0 for i in range(len(nums)+1)]
dp[1] = nums[0]
for i in range(2,len(nums)+1):
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1])
return dp[-1]
[leetcode]221.Maximal Square
動(dòng)態(tài)規(guī)劃，令A(yù)[i][j]表示的就是以(i,j)為右下角的最大的正方形的邊長(zhǎng)，時(shí)間復(fù)雜程度是?(???)
O
(
M
?
N
)
，空間復(fù)雜程度是?(???)
O
(
M
?
N
)
。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix:return 0
m,n = len(matrix),len(matrix[0])
dp = [[0 for j in range(n)] for i in range(m)]
res = 0
for i in range(m):
for j in range(n):
if i == 0:
dp[i][j] = int(matrix[i][j])
elif j == 0:
dp[i][j] = int(matrix[i][j])
else:
if matrix[i][j] == '1':
dp[i][j] = min(dp[i-1][j- 1],dp[i-1][j],dp[i][j- 1])+1
else:
dp[i][j] = 0
res = max(res,dp[i][j])
return res*res
注意這里dp[i][j]的更新條件是，matrix[i][j] == '1'，更新為dp[i-1][j- 1],dp[i-1][j],dp[i][j- 1]的最小值+1
[leetcode]309.Best Time to Buy and Sell Stock with Cooldown
兩個(gè)狀態(tài)：
１．在第i天買一支股票還能剩下的利潤(rùn)＝第(i-2)天銷售能夠剩余的利潤(rùn)－第i天股票的價(jià)錢．
２．在第i天賣一支股票總的利潤(rùn)＝第(i-1)天買股票剩下的最大利潤(rùn)＋當(dāng)前股票的價(jià)格．
也就是說(shuō)需要維護(hù)兩個(gè)狀態(tài)的信息，一個(gè)是買股票所得到的剩余最大利潤(rùn)，一個(gè)是賣出股票之后得到的最大利潤(rùn)，他們互相依賴對(duì)方的信息．
再來(lái)進(jìn)一步分析如何維持一個(gè)最大的利潤(rùn)．
對(duì)于買來(lái)說(shuō)，當(dāng)天是否買取決于買了之后是否比之前買所剩余的利潤(rùn)大，即狀態(tài)轉(zhuǎn)移方程為：
buy[i] = max(buy[i-1], sell[i-2] - prices[i-1]);
對(duì)于賣來(lái)說(shuō)，同樣當(dāng)天是否將這只股票賣掉取決于賣掉能否獲得更大的利潤(rùn)，狀態(tài)轉(zhuǎn)移方程為：
sell[i] = max(sell[i-1], buy[i-1] + prices[i-1]);
也可以根據(jù)題意，維護(hù)三個(gè)狀態(tài)，更容易理解。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# if not prices:
# return 0
# N = len(prices)
# buy = [0 for i in range(N+1)]
# sell = [0 for i in range(N+1)]
# buy[1] = -prices[0]
# for i in range(2,N+1):
# buy[i] = max(sell[i-2]-prices[i-1],buy[i-1])
# sell[i] = max(sell[i-1],buy[i-1]+prices[i-1])
# return sell[N]
if not prices:
return 0
N = len(prices)
rest = [0 for i in range(N)]
buy = [0 for i in range(N)]
sell = [0 for i in range(N)]
buy[0] = -prices[0]
for i in range(1,N):
rest[i] = max(rest[i-1],sell[i-1])
buy[i] = max(buy[i-1],rest[i-1]-prices[i])
sell[i] = max(sell[i-1],buy[i-1]+prices[i])
return sell[-1]
[leetcode]312.Burst Balloons
動(dòng)態(tài)規(guī)劃
設(shè)dp[i][j]為i到j(luò)這段區(qū)間所能得到的最大值，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = max(i < k < j) (dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
n = len(nums)
dp = [[0 for j in range(n)] for i in range(n)]
# dp[i][j]代表(i,j)區(qū)間內(nèi)取得的最大值 -->關(guān)鍵在于理解dp內(nèi)涵
for left in reversed(range(n)):
for right in range(left+1,n):
for i in range(left + 1, right):
dp[left][right] = max(dp[left][right],nums[left] * nums[i] * nums[right] +dp[left][i] + dp[i][right])
return dp[0][-1]
[leetcode]368.Largest Divisible Subset
使用一個(gè)一維DP，其含義是題目要求的數(shù)組，DP[i]的含義是，從0~i位置滿足題目的最長(zhǎng)數(shù)組。先用i遍歷每個(gè)數(shù)字，然后用j從后向前尋找能被nums[i]整除的數(shù)字，這樣如果判斷能整除的時(shí)候，再判斷dp[i] < dp[j] + 1，即對(duì)于以i索引結(jié)尾的最長(zhǎng)的數(shù)組是否變長(zhǎng)了。在變長(zhǎng)的情況下，需要更新dp[i]，同時(shí)使用parent[i]更新i的前面能整除的數(shù)字。另外還要統(tǒng)計(jì)對(duì)于整個(gè)數(shù)組最長(zhǎng)的子數(shù)組長(zhǎng)度。
知道了對(duì)于每個(gè)位置最長(zhǎng)的子數(shù)組之后，我們也就知道了對(duì)于0~n區(qū)間內(nèi)最長(zhǎng)的滿足題目條件的數(shù)組，最后需要再次遍歷，使用parent就能把正兒個(gè)數(shù)組統(tǒng)計(jì)輸出出來(lái)。因?yàn)檫@個(gè)最大的索引mx_index是對(duì)n而言的，所以輸出是逆序的。
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums: return []
N = len(nums)
nums.sort()
dp = [1] * N #LDS
parent = [0] * N
mx = 1
mx_index = -1
for i in range(N):
for j in reversed(range(i)):
if nums[i] % nums[j] == 0 and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
parent[i] = j
if dp[i] > mx:
mx = dp[i]
mx_index = i
res = []
for k in range(mx):
res.append(nums[mx_index])
mx_index = parent[mx_index]
return res[::-1]
這里的解題技巧是，在動(dòng)態(tài)規(guī)劃同時(shí)保存狀態(tài)，并且使用額外空間恢復(fù)現(xiàn)場(chǎng)。
[leetcode]486.Predict the Winner
動(dòng)態(tài)規(guī)劃
1.該問(wèn)題沒(méi)有直接比較一個(gè)選手所拿元素的和值，而是把問(wèn)題轉(zhuǎn)換為兩個(gè)選手所拿元素的差值。這一點(diǎn)很巧妙，是關(guān)鍵的一步。
2.找出遞推表達(dá)式：max(nums[beg] - partition(beg + 1, end), nums[end] - partition(beg, end + 1))
3.通過(guò)遞推表達(dá)式構(gòu)造遞歸算法是比較簡(jiǎn)單的。但是要構(gòu)造一個(gè)非遞歸的算法難度較大。對(duì)于非遞歸算法，首先在dp中賦初始值，這是我們解題的第一步。在這個(gè)問(wèn)題中，我們使用一個(gè)二位的數(shù)組dp來(lái)表示nums數(shù)組中任意開(kāi)始和結(jié)束位置兩人結(jié)果的差值。
初始的時(shí)候，我們僅僅知道對(duì)角線上的值。dp[i][i] = nums[i].這一點(diǎn)很好理解。接下來(lái)既然是求任意的開(kāi)始和結(jié)束，對(duì)于二維數(shù)組，那肯定是一個(gè)雙層的循環(huán)。通過(guò)dp中已知的元素和動(dòng)態(tài)規(guī)劃的遞推表達(dá)式，我們就可以構(gòu)造出我們的需要的結(jié)果。非遞歸的方式是從小問(wèn)題到大問(wèn)題的過(guò)程。
class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n = len(nums)
dp_f = [[0 for j in range(n)] for i in range(n)]
dp_g = [[0 for j in range(n)] for i in range(n)]
for i in reversed(range(n)):
for j in range(i,n):
if i==j:
dp_f[i][j] = nums[i]
else:
dp_f[i][j] = max(nums[i]+dp_g[i+1][j],
nums[j]+dp_g[i][j-1])
dp_g[i][j] = min(dp_f[i+1][j],dp_f[i][j-1])
return dp_f[0][-1] >= sum(nums)/2
[leetcode]494.Target Sum
該問(wèn)題求解數(shù)組中數(shù)字只和等于目標(biāo)值的方案?jìng)€(gè)數(shù)，每個(gè)數(shù)字的符號(hào)可以為正或負(fù)(減整數(shù)等于加負(fù)數(shù))。由于target和sum(nums)是固定值，因此原始問(wèn)題轉(zhuǎn)化為求解nums中子集的和等于sum(P)的方案?jìng)€(gè)數(shù)問(wèn)題，可轉(zhuǎn)化為背包問(wèn)題求解。
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
sum_ = sum(nums)
target = (sum_+S)/2
if target!=int(target):
return 0
if target>sum(nums):
return 0
target = int(target)
dp = [0 for i in range(target+1)]
dp[0] =1
for num in nums:
for i in reversed(range(num,target+1)):
dp[i] += dp[i-num]
return dp[-1]
[leetcode]516.Longest Palindromic Subsequence
設(shè)立一個(gè)len行l(wèi)en列的dp數(shù)組～dp[i][j]表示字符串i～j下標(biāo)所構(gòu)成的子串中最長(zhǎng)回文子串的長(zhǎng)度～最后我們需要返回的是dp[0][len-1]的值。
dp數(shù)組更新：首先i指針從尾到頭遍歷，j指針從i指針后面一個(gè)元素開(kāi)始一直遍歷到尾部～一開(kāi)始dp[i][i]的值都為1，如果當(dāng)前i和j所指元素相等，說(shuō)明能夠加到i～j的回文子串的長(zhǎng)度中，所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果當(dāng)前元素不相等，那么說(shuō)明這兩個(gè)i、j所指元素對(duì)回文串無(wú)貢獻(xiàn)，則dp[i][j]就是從dp[i+1][j]和dp[i][j-1]中選取較大的一個(gè)值即可。
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
if not s:
return 0
n = len(s)
dp = [[0 for j in range(n)] for i in range(n)]
for i in reversed(range(n)):
for j in range(i,n):
if i == j:dp[i][j] = 1
elif s[i] == s[j]:
dp[i][j] = dp[i+1][j-1]+2
else:
dp[i][j] = max(dp[i+1][j],dp[i][j-1])
return dp[0][-1]
[leetcode]576.Out of Boundary Paths
這道題給了我們一個(gè)二維的數(shù)組，某個(gè)位置放個(gè)足球，每次可以在上下左右四個(gè)方向中任意移動(dòng)一步，總共可以移動(dòng)N步，問(wèn)我們總共能有多少種移動(dòng)方法能把足球移除邊界，由于結(jié)果可能是個(gè)巨大的數(shù)，所以讓我們對(duì)一個(gè)大數(shù)取余。那么我們知道對(duì)于這種結(jié)果很大的數(shù)如果用遞歸解法很容易爆棧，所以最好考慮使用DP來(lái)解。那么我們使用一個(gè)三維的DP數(shù)組，其中dp[k][i][j]表示總共走k步，從(i,j)位置走出邊界的總路徑數(shù)。那么我們來(lái)找遞推式，對(duì)于dp[k][i][j]，走k步出邊界的總路徑數(shù)等于其周圍四個(gè)位置的走k-1步出邊界的總路徑數(shù)之和，如果周圍某個(gè)位置已經(jīng)出邊界了，那么就直接加上1，否則就在dp數(shù)組中找出該值，這樣整個(gè)更新下來(lái)，我們就能得出每一個(gè)位置走任意步數(shù)的出界路徑數(shù)了，最后只要返回dp[N][i][j]就是所求結(jié)果了。
class Solution:
def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
dp = [[0] * n for _ in range(m)]
for s in range(1, N + 1):
curStatus = [[0] * n for _ in range(m)]
for x in range(m):
for y in range(n):
v1 = 1 if x == 0 else dp[x - 1][y]
v2 = 1 if x == m - 1 else dp[x + 1][y]
v3 = 1 if y == 0 else dp[x][y - 1]
v4 = 1 if y == n - 1 else dp[x][y + 1]
curStatus[x][y] = (v1 + v2 + v3 + v4) % (10**9 + 7)
dp = curStatus
return dp[i][j]
背包問(wèn)題
[leetcode]322.Coin Change
使用動(dòng)態(tài)規(guī)劃，需要構(gòu)建一個(gè)長(zhǎng)度是amount + 1的dp數(shù)組，其含義是能夠成面額從0到amount + 1需要使用的最少硬幣數(shù)量。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [float('inf') for i in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
# if dp[i - coin] != float('inf'):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount]!= float('inf') else -1
[leetcode]474.Ones and Zeroes
這道題是從字符串集合中盡可能多的選出字符串并保證0和1個(gè)數(shù)不超過(guò)給定值，題目難度為Medium。
題目和0-1背包問(wèn)題大同小異，區(qū)別是這里限制0和1個(gè)數(shù)，而0-1背包問(wèn)題限制總重量，算是動(dòng)態(tài)規(guī)劃的經(jīng)典題目。
這里用dp[i][j][k]表示前i個(gè)字符串在0個(gè)數(shù)不超過(guò)j、1個(gè)數(shù)不超過(guò)k時(shí)最多能選取的字符串個(gè)數(shù)。統(tǒng)計(jì)第i個(gè)字符串中0和1個(gè)數(shù)分別為cnt0和cnt1，如果取第i個(gè)字符串則dp[i][j][k] = dp[i-1][j-cnt0][k-cnt1] + 1，如果不取第i個(gè)字符串則dp[i][j][k] = dp[i-1][j][k]，取兩者大的作為dp[i][j][k]的值。由于dp[i][j][k]只與dp[i-1][*][*]相關(guān)，所以這里可以重復(fù)使用???
m
?
n
個(gè)數(shù)據(jù)將空間復(fù)雜度降為?(???)
O
(
m
?
n
)
，只需在遍歷時(shí)從后向前遍歷即可。具體代碼：
class Solution:
def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
dp = [[0 for j in range(n+1)] for i in range(m+1)]
for str in strs:
cnt0 = str.count('0')
cnt1 = str.count('1')
for i in reversed(range(cnt0,m+1)):
for j in reversed(range(cnt1,n+1)):
dp[i][j] = max(dp[i][j],dp[i-cnt0][j-cnt1]+1)
return dp[-1][-1]
[leetcode]518.Coin Change 2
建立dp數(shù)組，保存能到達(dá)當(dāng)前amount的步數(shù)。逐個(gè)金額遍歷，看只用前i個(gè)金額能到達(dá)j的步數(shù)有多少，實(shí)現(xiàn)方法是累加起來(lái)dp[當(dāng)前amount - 第i個(gè)金額]，最后返回dp[amount]。
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0 for i in range(amount+1)]
dp[0] = 1
for coin in coins:
for i in range(coin,amount+1):
dp[i] += dp[i-coin]
return dp[-1]
總結(jié)
對(duì)于常見(jiàn)的動(dòng)態(tài)規(guī)劃問(wèn)題，有以下實(shí)例：
1.斐波那契數(shù)列(Climbing Stairs)
2.01背包問(wèn)題
3.最長(zhǎng)公共子序列
4.旅行商問(wèn)題 n!
Attention：
動(dòng)態(tài)規(guī)劃算法用到的題目存在很多套路
滾動(dòng)數(shù)組，狀態(tài)壓縮，（升維，單調(diào)性，四邊形不等式（高級(jí)套路））
本質(zhì)：先暴力，找冗余，去冗余
