122.买卖股票的时机II

122.买卖股票的时机II

文章目录

• • • 题目
    • 思路
    • 方法一:贪心策略
    • • 代码1
      • 运行结果1
      • 代码2
      • 运行结果2
    • 方法二：动态规划
    • • 代码
      • 运行结果
      • 代码2:简洁版
      • 运行结果2

题目

'''
Description: 122.买卖股票的最佳时机II
Autor: 365JHWZGo
Date: 2021-12-09 09:26:48
LastEditors: 365JHWZGo
LastEditTime: 2021-12-09 09:50:17
'''

思路

直观解题思路:
            这道题和昨天I版本的区别在于
                1.可以买入和卖出在同一天
                2.可以进行n次买入卖出，以保证获益最大
思路:
            1.确定dp数组以及下标含义
                dp[i]代表在第i天卖出所获得的最大利润
            2.确定递推公式
                dp[i] = max(dp[i-1]+prices[i]-prices[buyPoint],dp[i-1])
                经过方法一，我们已经知道：
                    当利润<=0时，我们需要更新买入点
                    当利润>0时，我们也可以更新买入点，因为-1+3-3+5，最后得出的结论看来，相当于没有更新买入点
            3.初始化dp数组
                dp[0]=0
            4.确定遍历顺序
                从前往后依次遍历
            5.举例推导
                prices=[7, 1, 5, 3, 6, 4]
                dp [0, 0, 4, 4, 7, 7]
                7

方法一:贪心策略 代码1

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0]*len(prices)
        buyPoint = 0
        for i in range(1, len(prices)):
            if prices[i]-prices[buyPoint] <= 0:
                dp[i] = dp[i-1]
            else:
                dp[i] = dp[i-1]+prices[i]-prices[buyPoint]
            buyPoint = i
        # print(dp)
        return dp[-1]

运行结果1

代码2

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        maxProfit = 0
        buyPoint = 0
        for i in range(1, len(prices)):
            if prices[i]-prices[buyPoint]>0:
               maxProfit+=prices[i]-prices[buyPoint]
            buyPoint = i
        return maxProfit

运行结果2

方法二：动态规划 代码

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0]*len(prices)
        buyPoint = 0
        for i in range(1, len(prices)):
            dp[i] = max(dp[i-1]+prices[i]-prices[buyPoint],dp[i-1])
            buyPoint = i
        # print(dp)
        return dp[-1]

运行结果

代码2:简洁版

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0]*len(prices)
        for i in range(1,len(prices)):
            dp[i] = max(dp[i-1]+prices[i]-prices[i-1],dp[i-1])
        # print(dp)
        return dp[-1]

运行结果2

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        dp = [0]
        for i in range(1,len(prices)):
            dp[0] = max(dp[0]+prices[i]-prices[i-1],dp[0])
        return dp[0]

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        maxProfit = 0
        for i in range(1,len(prices)):
            maxProfit = max(maxProfit+prices[i]-prices[i-1],maxProfit)
        return maxProfit