動態(tài)規(guī)劃
動態(tài)規(guī)劃的重點是：狀態(tài)轉(zhuǎn)移方程
1、判斷子序列
leetcode?392. 判斷子序列
class?Solution:
????def?isSubsequence(self,?s:?str,?t:?str)?->?bool:???
????????n=?len(s)?
????????m?=?len(t)
????????#行數(shù)是短的
????????#列數(shù)是長的
????????if?n==0:
????????????return?True
????????if?m==0:
????????????return?False
????????if?n>m:
????????????return?False
????????d=[?[0]?*?(m+1)?for?i?in?range(n+1)]
????????for?i?in?range(m+1):
????????????d[0][i]=True
????????for?j?in?range(1,n+1):
????????????d[j][0]=False
????????for?i?in?range(1,n+1):
????????????for?j?in?range(1,m+1):
????????????????if?s[i-1]==t[j-1]:
????????????????????d[i][j]=d[i-1][j-1]
????????????????else:
????????????????????d[i][j]=d[i][j-1]
????????return?d[n][m]
2、總和最大的連續(xù)數(shù)列
難度簡單69
給定一個整數(shù)數(shù)組，找出總和最大的連續(xù)數(shù)列，并返回總和。
class?Solution:
????def?maxSubArray(self,?nums:?List[int])?->?int:
????????if?len(nums)==0:
????????????return
????????if?len(nums)==1:
????????????return?nums[0]
????????s=nums[0]
????????max1=nums[0]
????????for?i?in?range(1,len(nums)):
????????????if?s>0:
????????????????s=s+nums[i]
????????????????max1=max(max1,s)
????????????else:
????????????????s=nums[i]
????????????????max1=max(max1,s)
????????return?max1
3、使用最小花費爬樓梯，到達下標n
leetcode:746. 使用最小花費爬樓梯
動態(tài)規(guī)劃：
狀態(tài)轉(zhuǎn)換方程：
到達下標i和下標i下的花費
d[0]=d[1]=0
d[i]=min(d[i-1]+cost[i],d[i-2]+cost[i])
代碼如下：
class?Solution:
????def?minCostClimbingStairs(self,?cost:?List[int])?->?int:
????????k=len(cost)
????????res=[]
????????if?k==1:
????????????return?cost[0]
????????if?k==2:
????????????return?min(cost[0],cost[1])
????????res.append(0)
????????res.append(0)
????????for?i?in?range(2,k+1):
????????????s=min(res[i-2]+cost[i-2],res[i-1]+cost[i-1])
????????????res.append(s)
????????return?res[k]
減小空間復(fù)雜度：利用滾動數(shù)組
class?Solution:
????def?minCostClimbingStairs(self,?cost:?List[int])?->?int:
????????k=len(cost)
????????res=[]
????????if?k==1:
????????????return?cost[0]
????????if?k==2:
????????????return?min(cost[0],cost[1])
????????res.append(0)
????????res.append(0)
????????pre=0
????????cur=0
????????for?i?in?range(2,k+1):
????????????s=min(pre+cost[i-2],cur+cost[i-1])
????????????pre=cur
????????????cur=s
????????return?cur
4、三步爬樓梯
leetcode?面試題 08.01. 三步問題
（1）動態(tài)規(guī)劃
class?Solution:
????def?waysToStep(self,?n:?int)?->?int:
????????if?n==1:
????????????return?1
????????if?n==2:
????????????return?2
????????if?n==3:
????????????return?4
????????f=[]
????????f.append(1)
????????f.append(2)
????????f.append(4)
????????base=1e9+7
????????for?i?in?range(3,n):
????????????s=((((f[i-1])+(f[i-2]))%base)+(f[i-3]))%base
????????????f.append(int(s))
????????return?f[n-1]
（2）滾動數(shù)組，不利用進行保存節(jié)省空間
class?Solution:
????def?waysToStep(self,?n:?int)?->?int:
????????if?n==1:
????????????return?1
????????if?n==2:
????????????return?2
????????if?n==3:
????????????return?4
????????f=[]
????????f.append(1)
????????f.append(2)
????????f.append(4)
????????base=1e9+7
????????three=1
????????two=2
????????one=4
????????for?i?in?range(3,n):
????????????tmp=int(((((one)+(two))%base)+(three))%base)
????????????three=two
????????????two=one
????????????one=tmp
????????return?tmp
5、買賣股票的最佳時機，只允許一次買入賣出
關(guān)鍵點是找個最小值
代碼的如下：
class?Solution:
????def?maxProfit(self,?prices:?List[int])?->?int:
???????if?len(prices)==0:
???????????return?0
???????max1=0
???????min1=prices[0]
???????for?i?in?range(1,len(prices)):
???????????min1=min(prices[i],min1)
???????????max1=max(max1,prices[i]-min1)
???????return?max1
6、區(qū)域和檢索
leetcode303. 區(qū)域和檢索 - 數(shù)組不可變
(1)暴力解法
class?NumArray:
????def?__init__(self,?nums:?List[int]):
????????self.nums=nums
????def?sumRange(self,?i:?int,?j:?int)?->?int:
????????return?sum(self.nums[i:j+1])
（2）動態(tài)規(guī)劃
class?NumArray:
????def?__init__(self,?nums:?List[int]):
????????self.nums=nums
????????self.d=[0]*len(self.nums)
????????if?len(self.nums)==0:
????????????return
????????self.d[0]=self.nums[0]
????????for?i?in?range(1,len(nums)):
????????????self.d[i]=self.d[i-1]+self.nums[i]
????def?sumRange(self,?i:?int,?j:?int)?->?int:
????????return?self.d[j]-self.d[i]+self.nums[i]
#?Your?NumArray?object?will?be?instantiated?and?called?as?such:
#?obj?=?NumArray(nums)
#?param_1?=?obj.sumRange(i,j)
