题目链接
题目描述
实现代码
动态规划思想
动态规划思想:跟买卖股票的最佳时机含冰冻期一样,每个i位置时刻只有两种情况,就是持有股票和不持有股票,因此可以设置如下两个状态:
- f[i][0]:在i位置不持有股票的最大利润
- f[i][1]:在i位置持有股票的最大利润
我们假设手续费在卖出的时候进行扣除,买入的时候不做计算
两个状态与第i-1位置的状态对应的状态转移方程如下:
- f[i][0] = max(f[i-1][0], f[i-1][1] + prices[i] - fee)
- f[i][1] = max(f[i-1][1], f[i-1][0] - prices[i])
对应的实现代码如下:
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]
for i in range(1, n):
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]
贪心思想
贪心思想:我们记buy表示每次获得最大利润的时候的买入价格,这里我们将手续费算在买入价格里,因此初始化buy = prices[i] + fee,因此对于遍历的每个位置i的有如下几种情况:
- prices[i] + fee < buy时:我们可以用更低的价格买入股票,因此更新buy
- prices[i] > buy时:我们可以将股票卖出,获取利润,同时将buy更新为prices[i],因为这可能并非当前最优卖出位置,同时即便是当前最优位置,我们还要找到下一个买入的最佳时机
这里需要注意,对于找到一次最佳买卖时机后,下一次进入买入,价格应该是跟前一次卖出的价格进行比较,如果当前价格加上手续费都比上一次最佳买卖时机的卖出价格低,那么就可以进行买入,因为一定相对于上次不卖出而言赚的更多
实现代码如下:
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
if n==1:
return 0
profit = 0
buy = prices[0] + fee
for i in range(1, n):
price = prices[i]
if price + fee < buy:
buy = price + fee
continue
elif price > buy:
profit += price - buy
buy = price
continue
return profit