文章目录
题目
'''
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
