動(dòng)態(tài)規(guī)劃主要思想：
如果需要解決一個(gè)給定的問(wèn)題，我們需要解決這個(gè)問(wèn)題的子問(wèn)題，再根據(jù)子問(wèn)題的解得到原問(wèn)題的解，可以考慮動(dòng)態(tài)優(yōu)化算法。動(dòng)態(tài)優(yōu)化往往適用于優(yōu)化遞歸問(wèn)題，減少重復(fù)運(yùn)算的過(guò)程。
動(dòng)態(tài)規(guī)劃的步驟
- 確定動(dòng)態(tài)規(guī)劃狀態(tài)
- 寫(xiě)出狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移表
- 考慮初始化條件
- 考慮輸出狀態(tài)
5.考慮時(shí)間和空間復(fù)雜度的優(yōu)化
動(dòng)態(tài)規(guī)劃練習(xí)1
leetcode #5 最長(zhǎng)回文子串
難度：中等
給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。
示例 1：輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個(gè)有效答案。
解決這道題容易想到需要通過(guò)遍歷字符串s的每一個(gè)子串，判斷其是否為回文序列，再記錄所有為回文序列中最大的一個(gè)。其中，判斷字符串是否為回文序列可以使用動(dòng)態(tài)規(guī)劃的思想：一個(gè)字符串s如果為回文序列，需要滿足s[0]==s[-1]并且s[1:-2]也為回文序列。
寫(xiě)出狀態(tài)轉(zhuǎn)移方程：
用i, j表示某子串的首位下標(biāo)，創(chuàng)建動(dòng)態(tài)規(guī)劃狀態(tài)轉(zhuǎn)移表dp
則dp[i][j] = True if s[i] == s[j] and dp[i+1][j-1] == True
初始化條件：
dp[i][j] = True if i==j, dp[i][j] = True if j == i + 1 and s[i] == s[j]
完整代碼如下：
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) == 0:
return ''
dp = [[False for _ in range(len(s))] for _ in range(len(s))]
res = (0,(0,0)) #記錄子串的長(zhǎng)度以及子串首尾坐標(biāo)結(jié)果
for l in range(len(s)): # l表示子串的長(zhǎng)度
for i in range(len(s)):
j = i + l
if j > len(s)-1:
break
if l == 0:
dp[i][j] = True
elif l == 1:
if s[i] == s[j]:
dp[i][j] = True
else:
if s[i] == s[j] and dp[i+1][j-1] == True:
dp[i][j] = True
if dp[i][j] == True:
if l > res[0]:
res = (l,(i, j)) #更新結(jié)果
i, j = res[1]
return s[i:j+1]
動(dòng)態(tài)規(guī)劃練習(xí)2
leetcode #72 編輯距離
難度：困難
給你兩個(gè)單詞 word1 和 word2，請(qǐng)你計(jì)算出將 word1 轉(zhuǎn)換成 word2 所使用的最少操作數(shù) 。
你可以對(duì)一個(gè)單詞進(jìn)行如下三種操作：
插入一個(gè)字符
刪除一個(gè)字符
替換一個(gè)字符
動(dòng)態(tài)規(guī)劃：
dp[i][j] 代表 word1 到 i 位置轉(zhuǎn)換成 word2 到 j 位置需要最少步數(shù)
所以，
當(dāng) word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
當(dāng) word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
其中，dp[i-1][j-1] 表示替換操作，dp[i-1][j] 表示刪除操作，dp[i][j-1] 表示插入操作。
第一行，第一列要單獨(dú)考慮:
第一行，是 word1 為空變成 word2 最少步數(shù)，就是插入操作；第一列，是 word2 為空，需要的最少步數(shù)，就是刪除操作
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n1 = len(word1)
n2 = len(word2)
dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
# 第一行
for j in range(1, n2 + 1):
dp[0][j] = dp[0][j-1] + 1
# 第一列
for i in range(1, n1 + 1):
dp[i][0] = dp[i-1][0] + 1
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1
return dp[-1][-1]
動(dòng)態(tài)規(guī)劃練習(xí)3
leetcode #198 打家劫舍
難度：簡(jiǎn)單
你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。
給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
狀態(tài)轉(zhuǎn)移：小偷在沿街偷盜時(shí)要對(duì)是否進(jìn)入每一家盜竊進(jìn)行判斷，判斷的規(guī)則應(yīng)該為：比較上上家為盜竊最后一家所得到的最大金額加上當(dāng)前家，以及上一家為盜竊的最后一家所得到的最大金額（因?yàn)椴荒鼙I竊相鄰的兩家），兩者取更大的一個(gè)作為選擇，即：
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
初始化條件：
dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
輸出：dp[-1]
代碼如下：
lass Solution:
def rob(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp = [nums[0], max(nums[0], nums[1])]
i = 2
while i <= len(nums)-1:
dp.append(max(nums[i] + dp[i-2],dp[i-1]))
i += 1
return dp[-1]
動(dòng)態(tài)規(guī)劃練習(xí)4
leetcode #213 打家劫舍2
難度：中等
這道題是198的一個(gè)小升級(jí)，不能同時(shí)打劫第一家和最后一家，其實(shí)只需要把nums拆分為nums[0:-1]和nums[1:]再分別利用動(dòng)態(tài)規(guī)劃求解，最后比較兩個(gè)結(jié)果大小即可代碼如下：
class Solution(object):
def dp(self,nums):
if len(nums) ==1:
return nums[0]
elif len(nums) ==2:
return max(nums[0], nums[1])
dp = [0]*len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
return dp[-1]
def rob(self, nums):
if len(nums) == 0:
return 0
elif len(nums) ==1:
return nums[0]
# 拆分?jǐn)?shù)組
# sub1 nums[0] to nums[N-2]
# sub2 nums[1] to nums[N-1]
sub1 = nums[0:-1]
sub2 = nums[1:]
return max(self.dp(sub1), self.dp(sub2))
動(dòng)態(tài)規(guī)劃練習(xí)5
leetcode #516 最長(zhǎng)回文子序列
難度：中等
狀態(tài)轉(zhuǎn)移：
dp矩陣記錄首尾坐標(biāo)為i,j的子字符串中最長(zhǎng)回文序列的長(zhǎng)度
如果s[i] == s[j] 則dp[i][j]等于去掉首尾的子字符串的最長(zhǎng)回文序列的長(zhǎng)度
否則，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
初始化：
如果子字符串長(zhǎng)度為1，則其本身就是回文子序列，dp[i][i] = 1
代碼如下：
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
return dp[0][n-1]
動(dòng)態(tài)規(guī)劃練習(xí)6
leetcode #674 最長(zhǎng)連續(xù)遞增序列
難度：簡(jiǎn)單
給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組，找到最長(zhǎng)且連續(xù)的的遞增序列，并返回該序列的長(zhǎng)度。
示例:
輸入: [1,3,5,4,7]
輸出: 3
解釋: 最長(zhǎng)連續(xù)遞增序列是 [1,3,5], 長(zhǎng)度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的，因?yàn)?和7在原數(shù)組里被4隔開(kāi)。
設(shè)dp[i][j]記錄首尾下標(biāo)為i，j的子序列是否為連續(xù)遞增序列和該子序列的長(zhǎng)度
狀態(tài)轉(zhuǎn)移：
dp[i][j][0] = True if nums[j] > nums[j-1] and dp[i][j-1][0] == True else False
考慮優(yōu)化時(shí)間空間復(fù)雜度，用變量count記錄當(dāng)前序列連續(xù)遞增的元素個(gè)數(shù)，一旦不滿足連續(xù)遞增則count變回1，再利用變量res在遍歷每個(gè)元素的時(shí)候記錄count所達(dá)到的最大值。
這樣時(shí)間復(fù)雜度降為O(n)，空間復(fù)雜度降為O(1)
代碼如下：
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return 1
count = 1
res = 1
for i in range(1,len(nums)):
if nums[i] > nums[i-1]:
count += 1
else:
count = 1
res = max(res, count)
return res
