02-16：动态规划题总结
1、动态规划解除数博弈
代码如下：
class Solution:
def divisorGame(self, N: int) -> bool:
if N==1:
return False
if N==2:
return True
if N==3:
return False
d=[0]*(N)
d[0]=False
for i in range(1,N):
d[i]=bool(1-d[i-1])
return d[N-1]
2、不连续求总和，同一个问题和解法
代码如下：
class Solution:
def massage(self, nums: List[int]) -> int:
k=len(nums)
if k==0:
return 0
if k==1:
return nums[0]
if k==2:
return max(nums[0],nums[1])
d=[0]*k
d[0]=nums[0]
d[1]=max(nums[0],nums[1])
for i in range(2,k):
d[i]=max(d[i-1],d[i-2]+nums[i])
return d[k-1]
（2）打家劫舍
代码如下：
class Solution:
def rob(self, nums: List[int]) -> int:
k=len(nums)
if k==0:
return 0
if k==1:
return nums[0]
if k==2:
return max(nums[0],nums[1])
d=[0]*k
d[0]=nums[0]
d[1]=max(nums[0],nums[1])
for i in range(2,k):
d[i]=max(d[i-1],d[i-2]+nums[i])
return d[k-1]
2、整数拆分问题
代码如下：
class Solution:
def integerBreak(self, n: int) -> int:
d=[0]*(n+1)
if n==2:
return 1
if n==3:
return 2
d[2]=1
d[3]=2
for i in range(4,n+1):
for j in range(i):
d[i]=max(d[i],(i-j)*j,d[i-j]*j)
return d[-1]
核心思想
3、打家劫舍升级版，房屋首尾相连
代码如下：
class Solution:
def rob(self, nums: List[int]) -> int:
k=len(nums)
if k==0:
return 0
if k==1:
return nums[0]
if k==2:
return max(nums[0],nums[1])
def d(s):
k1=len(s)
d=[0]*k1
d[0]=s[0]
d[1]=max(s[0],s[1])
for i in range(2,k1):
d[i]=max(d[i-2]+s[i],d[i-1])
return d[k1-1]
return max(d(nums[:k-1]),d(nums[1:]))
4、买卖股票的最佳时机（次数不限且有手续费）714. 买卖股票的最佳时机含手续费
关键点：把手续费算买入的价格的一部分：
代码如下：
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
buy = prices[0]+fee
profit = 0
for i in range(1, n):
if prices[i] +fee < buy:
buy = prices[i]+fee
elif prices[i] > buy:
profit += prices[i] - buy
buy = prices[i]
return profit
