309. 最佳买卖股票时机含冷冻期
- 思路
- example
- 不限交易次数
- 复习：
dp[i][0]: 第i天持有股票 最大利润
dp[i][1]: 第i天不持有股票 最大利润
- 现在多了一个冷冻期 (不持有状态分为两类：当天不卖出，当天卖出)
dp[i][0]: 第i天持有股票 最大利润
dp[i][1]: 第i天不持有股票并且第i天不卖出（之前已卖出） 最大利润。 这个时候说明第i+1天不是冷冻期.
dp[i][2]: 第i天不持有股票并且第i天卖出 最大利润。 这个时候说明第i+1天是冷冻期.
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
dp = [[0]*3 for _ in range(len(prices))]
dp[0][0] = -prices[0]
dp[0][1] = 0
dp[0][2] = -float('inf') # 不可行，赋值“最小数”
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
# 前一天持有 前一天不持有且今天不是冷冻期
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
# 前一天不持有（今天非冷冻）， 前一天不持有（今天冷冻）
dp[i][2] = dp[i-1][0] + prices[i]
return max(dp[-1][1], dp[-1][2])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
dp[0][2] = 0 # 这样也可以
for i in range(1, n):
for j in range(3):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0]+prices[i]
return max(dp[n-1][1], dp[n-1][2])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = [-prices[0], 0, 0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + prices[i]
return max(dp[n-1])
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0] = [-prices[0], 0, 0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][2])
dp[i][2] = dp[i-1][0] + prices[i]
return max(dp[n-1])
714. 买卖股票的最佳时机含手续费
- 思路
- example
- 不限交易次数
- 复习: 不含手续费情况
dp[i][0]: 第i天持有股票 最大利润
dp[i][1]: 第i天不持有股票 最大利润
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])
- 现在多了一个手续费 (e.g., 卖出时计入）
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
- 复杂度. 时间：O(n), 空间: O(n)
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
dp = [[0]*2 for _ in range(len(prices))]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, len(prices)):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
return dp[-1][1]
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0][0] = -prices[0]
dp[0][1] = 0
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
return max(dp[n-1])
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
dp = [[0 for _ in range(2)] for _ in range(n)]
dp[0] = [-prices[0], 0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee)
return max(dp[n-1])
