第九章 动态规划Part9
目录
- 任务
- 188. 买卖股票的最佳时机 IV
- 思路
- 309. 买卖股票的最佳时机含冷冻期
- 思路
- 714. 买卖股票的最佳时机含手续费
- 思路
- 188. 买卖股票的最佳时机 IV
任务
188. 买卖股票的最佳时机 IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路
实际上是至多交易两次的通用版本，至多交易k次。引入循环变量j，类比123.买卖股票的最佳时机III，关注奇数和偶数时的买入卖出逻辑即可。
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
dp = [[0] *(2*k + 1) for _ in range(len(prices))]
j = 1
while j < 2*k:
dp[0][j] = -prices[0]
j+=2
for i in range(1,len(prices)):
for j in range(1,2*k+1):
if j % 2 != 0: # 奇数，持有
dp[i][j] = max(dp[i-1][j-1]-prices[i],dp[i-1][j])
else: #偶数，不持有
dp[i][j] = max(dp[i-1][j-1]+prices[i],dp[i-1][j])
return dp[len(prices)-1][2*k]
309. 买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路
类比122.买卖股票的最佳时机II,这个是多次交易不含冷冻期，含有冷冻期只是在推导dp[i][0]的当天买入的情况有点差别，对于含冷冻期，当天买入说明昨天一定是冷冻期或者未操作，而前天一定是未持有状态，这是与不含冷冻期的差别。另外注意因为有i-2,所以初始化时需要多初始化一行dp[1][0]和dp[1][1]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp[i][0] 表示第i天持有股票获得的最大现金 (持有：包含当天买入和之前买入)
# dp[i][1] 表示第i天不持有股票获得的最大现金（不持有：包含当天卖出和之前卖出）
if len(prices) < 2: return 0
dp = [[0] * 2 for _ in range(len(prices))]
dp[0][0] =-prices[0]
dp[0][1] = 0
dp[1][0] = max(-prices[0],-prices[1])
dp[1][1] = max(0,prices[1]-prices[0])
for i in range(1,len(prices)):
dp[i][0] = max(dp[i-2][1]-prices[i],dp[i-1][0]) #如果当天买入，则看前天的状态（前天一定不持股）
dp[i][1] = max(prices[i]+dp[i-1][0],dp[i-1][1])
return dp[len(prices)-1][1]
714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
思路
类比122.买卖股票的最佳时机II，只是当太难卖出时多了一笔手续费，减去即可。
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
# dp[i][0] 表示第i天持有股票获得的最大现金 (持有：包含当天买入和之前买入)
# dp[i][1] 表示第i天不持有股票获得的最大现金（不持有：包含当天卖出和之前卖出）
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][1]-prices[i],dp[i-1][0])
dp[i][1] = max(prices[i]+dp[i-1][0]-fee,dp[i-1][1])
return dp[len(prices)-1][1]