02-16：动态规划题总结

1、动态规划解除数博弈

1025. 除数博弈

代码如下：

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、不连续求总和，同一个问题和解法

（1）面试题 17.16. 按摩师

代码如下：

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、整数拆分问题

343. 整数拆分

代码如下：

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