動(dòng)態(tài)規(guī)劃主要思想：
如果需要解決一個(gè)給定的問題，我們需要解決這個(gè)問題的子問題愿汰，再根據(jù)子問題的解得到原問題的解困后，可以考慮動(dòng)態(tài)優(yōu)化算法乐纸。動(dòng)態(tài)優(yōu)化往往適用于優(yōu)化遞歸問題，減少重復(fù)運(yùn)算的過程操灿。
動(dòng)態(tài)規(guī)劃的步驟
- 確定動(dòng)態(tài)規(guī)劃狀態(tài)
- 寫出狀態(tài)轉(zhuǎn)移方程和狀態(tài)轉(zhuǎn)移表
- 考慮初始化條件
- 考慮輸出狀態(tài)
5.考慮時(shí)間和空間復(fù)雜度的優(yōu)化
動(dòng)態(tài)規(guī)劃練習(xí)1
leetcode #5 最長回文子串
難度：中等
給定一個(gè)字符串 s锯仪，找到 s 中最長的回文子串。你可以假設(shè) s 的最大長度為 1000趾盐。
示例 1：輸入: "babad" 輸出: "bab" 注意: "aba" 也是一個(gè)有效答案。
解決這道題容易想到需要通過遍歷字符串s的每一個(gè)子串小腊，判斷其是否為回文序列救鲤，再記錄所有為回文序列中最大的一個(gè)。其中秩冈，判斷字符串是否為回文序列可以使用動(dòng)態(tài)規(guī)劃的思想：一個(gè)字符串s如果為回文序列本缠，需要滿足s[0]==s[-1]并且s[1:-2]也為回文序列。
寫出狀態(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)) #記錄子串的長度以及子串首尾坐標(biāo)結(jié)果
for l in range(len(s)): # l表示子串的長度
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 最長回文子序列
難度：中等
狀態(tài)轉(zhuǎn)移：
dp矩陣記錄首尾坐標(biāo)為i,j的子字符串中最長回文序列的長度
如果s[i] == s[j] 則dp[i][j]等于去掉首尾的子字符串的最長回文序列的長度
否則拥娄，dp[i][j] = max(dp[i][j-1], dp[i+1][j])
初始化：
如果子字符串長度為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 最長連續(xù)遞增序列
難度：簡(jiǎn)單
給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組稚瘾，找到最長且連續(xù)的的遞增序列牡昆，并返回該序列的長度。
示例:
輸入: [1,3,5,4,7]
輸出: 3
解釋: 最長連續(xù)遞增序列是 [1,3,5], 長度為3摊欠。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續(xù)的丢烘，因?yàn)?和7在原數(shù)組里被4隔開。
設(shè)dp[i][j]記錄首尾下標(biāo)為i些椒，j的子序列是否為連續(xù)遞增序列和該子序列的長度
狀態(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
