動態規劃法（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-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()];

遞推式子如下了：

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：

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

滾動陣列，狀態壓縮，（升維，單調性，四邊形不等式（高階套路））

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

引用一下別的大佬寫的介紹

搞清楚什麼是動態規劃，和什麼時候用動態規劃。

集合儲存狀態+狀態轉移方程

超級樓梯

共兩種爬樓方式——一次上一個臺階&一次上兩個臺階，問上到第n階臺階的方法共多少種。

設狀態dp[i]為上i階臺階的方法種數，dp[1]=1;dp[2]=1;

狀態轉移方程 dp[i]=dp[i-1]+dp[i-2];//上一階和兩階

有了該遞推式，我們就不用遞迴暴力解決了。（遞迴開銷是真的大

不同路徑

dp[i][j]為到單元格(i,j)的方法數，dp[0][]=1;dp[][0]=1;

dp[i][j]=dp[i-1][j]+dp[i][j-1];//向下走和向右走

　　

public int uniquePaths(int m, int n) {

int[][] dp = new int[m][n];

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

if (i == 0 || j == 0)

dp[i][j] = 1;

else {

dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

}

}

}

return dp[m - 1][n - 1];

}

進階：不同路徑 II

public int uniquePathsWithObstacles(int[][] obstacleGrid) {

int row=obstacleGrid.length;

int col=obstacleGrid[0].length;

int[][] dp=new int[row][col];

if(obstacleGrid[0][0]==1){

return 0;

}

for(int i=0;i<row;i++){

for(int j=0;j<col;j