動態規劃如何測試是否超時？

動態規劃法（dynamic programming）通常用于求解最優化問題（optimization problem），它適用于那些子問題相互重疊的情況，即子問題不獨立，不同的子問題具有公共的子子問題（就是子問題的子問題）。這顯然與分治法是不同的，分治法將問題劃分為不重疊的子問題，然后分別求解這些子問題，最后將這些問題合并得到最終的解。

對于具有公共子問題的情況，分治法會做很多不必要的工作，它會多次求解同一子子問題。動態規劃法卻不一樣，對每個子子問題它只會求解一次，將其保存在一個表格中，避免了不必要的重復計算。

利用動態規劃法求出來的是這個問題的一個最優解（an optimal solution），記住這里求解的只是最優解（the optimal solution）中的一個，因為最優解可能有多個。

適用dp的問題必須滿足最優化原理和無后效性。

1.最優化原理：如果問題的最優解包含的子問題的解也是最優解，則稱該問題具有最有子結構，即滿足最優化原理。（也即子結構最優時通過選擇后一定最優）

2.無后效性：某階段的狀態一旦確定，則此后過程的演變不再受此前各種狀態及決策的影響，簡單的說，就是“未來與過去無關”，當前的狀態是此前歷史的一個完整總結，此前的歷史只能通過當前的狀態去影響過程未來的演變。

3.重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）。其實本質上dp就是一個以空間換時間的做法，為了降低時間復雜度，不對子問題進行重復計算，其必須存儲過程中的各種狀態。

動態規劃可以從暴力枚舉逐步優化得到。問題求解的各個方法:暴力枚舉->遞歸->備忘錄算法->動歸算法

[leetcode]10.Regular Expression Matching

對于p字符串有點、字母、點.

.

、字母?

?

四種元素，點匹配任意一個字母，字母匹配相同的一個字母，點?

?

匹配任意字母（可以是任意不同字母，例如.?

.

?

匹配abc），字母?

?

匹配連續任意個相同字母，值得注意的是?

?

的任意包括0個。由于?

?

可以匹配任意個，造成檢驗s和p是否完全匹配的時候難以確定究竟?

?

匹配幾個字母合適，這正是本題的關鍵點。

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

動態規劃的關鍵是要得到遞推關系式。對于本題，到達某一點的路徑數等于到達它上一點的路徑數與它左邊的路徑數之和。也即，起點到點(i, j)的路徑總數：ways[i][j] = 起點到點(i, j-1)的總數：ways[i][j-1] + 起點到點(i-1, j)總數：ways[i-1][j]。于是我們就得到遞推關系式：????[?][?]=????[?][??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

編輯距離也是一個極其重要和經典的問題了。

這個算法計算的是將s[1…i]轉換為t[1…j]（例如將kitten轉換為sitting）所需最少的操作數（也就是所謂的編輯距離），這個操作數被保存在d[i,j]（d代表的就是上圖所示的二維數組）中。

在第一行與第一列肯定是正確的，這也很好理解，例如我們將kitten轉換為空字符串，我們需要進行的操作數為kitten的長度（所進行的操作為將kitten所有的字符丟棄）。

我們對字符可能進行的操作有三種：

如果我們可以使用k個操作數把s[1…i]轉換為t[1…j-1]，我們只需要把t[j]加在最后面就能將s[1…i]轉換為t[1…j]，操作數為k+1

如果我們可以使用k個操作數把s[1…i-1]轉換為t[1…j]，我們只需要把s[i]從最后刪除就可以完成轉換，操作數為k+1

如果我們可以使用k個操作數把s[1…i-1]轉換為t[1…j-1]，我們只需要在需要的情況下（s[i] != t[j]）把s[i]替換為t[j]，所需的操作數為k+cost（cost代表是否需要轉換，如果s[i]==t[j]，則cost為0，否則為1）。

將s[1…n]轉換為t[1…m]當然需要將所有的s轉換為所有的t，所以，d[n,m]（表格的右下角）就是我們所需的結果。

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的方法，而不要求把每種方法都列出來，所以用DP。假設當前的元素為Z，他前面的兩個為XY， i.e.XYZ。

1.如果Z=0, 并且Y=1 or 2。 那么對應于Z的DP值等于X的DP值，因為對于10只有一種解釋方式，所以 DP[i] = DP[i-2]。

2.如果 YZ 位于[11, 19] 或者 [21, 26] 這兩個range中，那么顯然對于這個兩位數我們有兩種decode的方式，也就是說 DP[i] = DP[i-1]+DP[i-2], 注意這里不是DP[i] = DP[i-1]+1。 例如 1212中的最后一個2。

3.如果X不是0， 例如YZ = 81。 那么DP[i] = DP[i-1].

最后注意的是由于2中我們要取到DP[i-2]，所以我們在初始DP list的時候在最前面加上一個1。由于加上了最前面的這個1。所以當DP[i]對應的是s[i-1]。 YZ對應的就是 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中任意一個就遞歸下去。但是會超時。

因此考慮用動態規劃做。

s1, s2只有兩個字符串，因此可以展平為一個二維地圖，判斷是否能從左上角走到右下角。

當s1到達第i個元素，s2到達第j個元素:

地圖上往右一步就是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個和T的前j個的符合個數，那么最后目標就是dp[S.size()][T.size()];

初始化，j = 0 時候，dp[i][0] = 1，因為所有的都可以通過刪除所有變成空字符，并且只有一種。

遞推式子如下了：

i和j都從1開始，且j不能大于i，因為匹配的長度至少為1開始，j大于i無意義

如果 ?==?

i

==

j

那么 dp[i][j] = S.substr(0, i) == T.substr(0, j);

如果 ?!=?

i

!

=

j

分兩種情況

S[i-1] != T[j-1] 時，也就是加入不加入i的影響是一樣的，那么 dp[i][j] = dp[i - 1][j];

S[i-1] == T[j-1] 時，那么當前字符可選擇匹配或者是不匹配，所以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

這道是買股票的最佳時間系列問題中最難最復雜的一道，前面兩道 Best Time to Buy and Sell Stock 和 Best Time to Buy and Sell Stock II 的思路都非常的簡潔明了，算法也很簡單。而這道是要求最多交易兩次，找到最大利潤，還是需要用動態規劃Dynamic Programming來解，而這里我們需要兩個遞推公式來分別更新兩個變量local和global.我們其實可以求至少k次交易的最大利潤，找到通解后可以設定 k = 2，即為本題的解答。我們定義local[i][j]為在到達第i天時最多可進行j次交易并且最后一次交易在最后一天賣出的最大利潤，此為局部最優。然后我們定義global[i][j]為在到達第i天時最多可進行j次交易的最大利潤，此為全局最優。它們的遞推式為：

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])

其中局部最優值是比較前一天并少交易一次的全局最優加上大于0的差值，和前一天的局部最優加上差值中取較大值，而全局最優比較局部最優和前一天的全局最優，代碼如下：

class Solution:

def maxProfit(self, prices: List[int]) -> int:

if not prices:

return 0

# 二維數組

# 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]

# 一維數組

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]

其實可以總結為兩個狀態的DP，分別代表當天必須賣的利潤和不一定當天賣的利潤。

[leetcode]132.Palindrome Partitioning II

輸入一個字符串，將其進行分割，分割后各個子串必須是“回文”結構，要求最少的分割次數。顯然，為了求取最少分割次數，一個簡單的思路是窮盡所有分割情況，再從中找出分割后可構成回文子串且次數最少的分割方法。

對于一個字符串，我們需要考慮所有可能的分割，這個問題可以抽象成一個DP問題，對于一個長度為n的字符串，設DP[i][j]表示第i個字符到第j個字符是否構成回文，若是，則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

動態規劃。dp[i]表示字符串s[:i]能否拆分成符合要求的子字符串。我們可以看出，如果s[j:i]在給定的字符串組中，且dp[j]為True（即字符串s[:j]能夠拆分成符合要求的子字符串），那么此時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)]

以上關于字符串的動態規劃，我們可以發現：對于字符串求最長/短，最大/小的最優解，我們可以通過分析子問題來分解問題的求解，通過子問題的求解來完成整體的最優解。

[leetcode]174.Dungeon Game

自底向上的動態規劃

在走完最后一個房間的時候血量至少要剩下１，因此最后的狀態可以當成是初始狀態，由后往前依次決定在每一個位置至少要有多少血量, 這樣一個位置的狀態是由其下面一個和和左邊一個的較小狀態決定 ．因此一個基本的狀態方程是: 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

動態規劃DP。本質相當于在一列數組中取出一個或多個不相鄰數，使其和最大。

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

這個題多了環的條件，在這個約束下就多了個不同時偷第一個和最后一個就可以了。所以，兩種偷的情況：第一種不偷最后一個房間，第二種不偷第一個房間，求這兩種偷法能獲得的最大值。

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

動態規劃，令A[i][j]表示的就是以(i,j)為右下角的最大的正方形的邊長，時間復雜程度是?(???)

O

(

M

?

N

)

，空間復雜程度是?(???)

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

兩個狀態：

１．在第i天買一支股票還能剩下的利潤＝第(i-2)天銷售能夠剩余的利潤－第i天股票的價錢．

２．在第i天賣一支股票總的利潤＝第(i-1)天買股票剩下的最大利潤＋當前股票的價格．

也就是說需要維護兩個狀態的信息，一個是買股票所得到的剩余最大利潤，一個是賣出股票之后得到的最大利潤，他們互相依賴對方的信息．

再來進一步分析如何維持一個最大的利潤．

對于買來說，當天是否買取決于買了之后是否比之前買所剩余的利潤大，即狀態轉移方程為：

buy[i] = max(buy[i-1], sell[i-2] - prices[i-1]);

對于賣來說，同樣當天是否將這只股票賣掉取決于賣掉能否獲得更大的利潤，狀態轉移方程為：

sell[i] = max(sell[i-1], buy[i-1] + prices[i-1]);

也可以根據題意，維護三個狀態，更容易理解。

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

動態規劃

設dp[i][j]為i到j這段區間所能得到的最大值，狀態轉移方程為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)區間內取得的最大值 -->關鍵在于理解dp內涵

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

使用一個一維DP，其含義是題目要求的數組，DP[i]的含義是，從0~i位置滿足題目的最長數組。先用i遍歷每個數字，然后用j從后向前尋找能被nums[i]整除的數字，這樣如果判斷能整除的時候，再判斷dp[i] < dp[j] + 1，即對于以i索引結尾的最長的數組是否變長了。在變長的情況下，需要更新dp[i]，同時使用parent[i]更新i的前面能整除的數字。另外還要統計對于整個數組最長的子數組長度。

知道了對于每個位置最長的子數組之后，我們也就知道了對于0~n區間內最長的滿足題目條件的數組，最后需要再次遍歷，使用parent就能把正兒個數組統計輸出出來。因為這個最大的索引mx_index是對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]

這里的解題技巧是，在動態規劃同時保存狀態，并且使用額外空間恢復現場。

[leetcode]486.Predict the Winner

動態規劃

1.該問題沒有直接比較一個選手所拿元素的和值，而是把問題轉換為兩個選手所拿元素的差值。這一點很巧妙，是關鍵的一步。

2.找出遞推表達式：max(nums[beg] - partition(beg + 1, end), nums[end] - partition(beg, end + 1))

3.通過遞推表達式構造遞歸算法是比較簡單的。但是要構造一個非遞歸的算法難度較大。對于非遞歸算法，首先在dp中賦初始值，這是我們解題的第一步。在這個問題中，我們使用一個二位的數組dp來表示nums數組中任意開始和結束位置兩人結果的差值。

初始的時候，我們僅僅知道對角線上的值。dp[i][i] = nums[i].這一點很好理解。接下來既然是求任意的開始和結束，對于二維數組，那肯定是一個雙層的循環。通過dp中已知的元素和動態規劃的遞推表達式，我們就可以構造出我們的需要的結果。非遞歸的方式是從小問題到大問題的過程。

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

該問題求解數組中數字只和等于目標值的方案個數，每個數字的符號可以為正或負(減整數等于加負數)。由于target和sum(nums)是固定值，因此原始問題轉化為求解nums中子集的和等于sum(P)的方案個數問題，可轉化為背包問題求解。

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

設立一個len行len列的dp數組～dp[i][j]表示字符串i～j下標所構成的子串中最長回文子串的長度～最后我們需要返回的是dp[0][len-1]的值。

dp數組更新：首先i指針從尾到頭遍歷，j指針從i指針后面一個元素開始一直遍歷到尾部～一開始dp[i][i]的值都為1，如果當前i和j所指元素相等，說明能夠加到i～j的回文子串的長度中，所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果當前元素不相等，那么說明這兩個i、j所指元素對回文串無貢獻，則dp[i][j]就是從dp[i+1][j]和dp[i][j-1]中選取較大的一個值即可。

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

這道題給了我們一個二維的數組，某個位置放個足球，每次可以在上下左右四個方向中任意移動一步，總共可以移動N步，問我們總共能有多少種移動方法能把足球移除邊界，由于結果可能是個巨大的數，所以讓我們對一個大數取余。那么我們知道對于這種結果很大的數如果用遞歸解法很容易爆棧，所以最好考慮使用DP來解。那么我們使用一個三維的DP數組，其中dp[k][i][j]表示總共走k步，從(i,j)位置走出邊界的總路徑數。那么我們來找遞推式，對于dp[k][i][j]，走k步出邊界的總路徑數等于其周圍四個位置的走k-1步出邊界的總路徑數之和，如果周圍某個位置已經出邊界了，那么就直接加上1，否則就在dp數組中找出該值，這樣整個更新下來，我們就能得出每一個位置走任意步數的出界路徑數了，最后只要返回dp[N][i][j]就是所求結果了。

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]

背包問題

[leetcode]322.Coin Change

使用動態規劃，需要構建一個長度是amount + 1的dp數組，其含義是能夠成面額從0到amount + 1需要使用的最少硬幣數量。

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個數不超過給定值，題目難度為Medium。

題目和0-1背包問題大同小異，區別是這里限制0和1個數，而0-1背包問題限制總重量，算是動態規劃的經典題目。

這里用dp[i][j][k]表示前i個字符串在0個數不超過j、1個數不超過k時最多能選取的字符串個數。統計第i個字符串中0和1個數分別為cnt0和cnt1，如果取第i個字符串則dp[i][j][k] = dp[i-1][j-cnt0][k-cnt1] + 1，如果不取第i個字符串則dp[i][j][k] = dp[i-1][j][k]，取兩者大的作為dp[i][j][k]的值。由于dp[i][j][k]只與dp[i-1][*][*]相關，所以這里可以重復使用???

m

?

n

個數據將空間復雜度降為?(???)

O

(

m

?

n

)

，只需在遍歷時從后向前遍歷即可。具體代碼：

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數組，保存能到達當前amount的步數。逐個金額遍歷，看只用前i個金額能到達j的步數有多少，實現方法是累加起來dp[當前amount - 第i個金額]，最后返回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]

總結

對于常見的動態規劃問題，有以下實例：

1.斐波那契數列(Climbing Stairs)

2.01背包問題

3.最長公共子序列

4.旅行商問題 n!

Attention：

動態規劃算法用到的題目存在很多套路

滾動數組，狀態壓縮，（升維，單調性，四邊形不等式（高級套路））

本質：先暴力，找冗余，去冗余