代码随想录训练营 Day42打卡 动态规划 part09
一、力扣188.买卖股票的最佳时机IV
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
这道题是典型的股票买卖问题，不过与常规的股票买卖问题不同，这里允许最多进行 k 笔交易。我们需要设计一个动态规划算法，来计算在最多进行 k 笔交易的情况下，可以获得的最大利润。
动态规划状态定义
dp[i][j] 表示在第 i 天结束后，处于状态 j 时的最大利润。
j 的状态定义如下：
j = 0：表示没有进行任何操作。
j = 1：表示第一次买入。
j = 2：表示第一次卖出。
j = 3：表示第二次买入。
j = 4：表示第二次卖出。
以此类推。
注意：在 j 中，奇数表示“买入”状态，偶数表示“卖出”状态。
状态转移方程
对于 dp[i][1]，即表示在第 i 天结束时的第一次买入状态：
可能是第 i 天买入股票：dp[i][1] = dp[i-1][0] - prices[i]
也可能是在第 i-1 天已经买入：dp[i][1] = dp[i-1][1]
取这两者的最大值：dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
对于 dp[i][2]，即表示在第 i 天结束时的第一次卖出状态：
可能是第 i 天卖出股票：dp[i][2] = dp[i-1][1] + prices[i]
也可能是在第 i-1 天已经卖出：dp[i][2] = dp[i-1][2]
取这两者的最大值：dp[i][2] = max(dp[i-1][1] + prices[i], dp[i-1][2])
同理，可以推导出其余状态的转移方程。
初始条件
dp[0][0] = 0 表示第 0 天没有操作。
dp[0][1] = -prices[0] 表示第 0 天第一次买入。
dp[0][2] = 0 表示第 0 天第一次卖出（实际上不可能在这一天卖出）。
dp[0][3] = -prices[0] 表示第 0 天第二次买入。
dp[0][4] = 0 表示第 0 天第二次卖出（同样不可能）。
代码实现
from typing import List
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
# 创建一个大小为 len(prices) x (2*k + 1) 的二维 dp 数组
dp = [[0] * (2 * k + 1) for _ in range(len(prices))]
# 初始化：第 0 天的状态
for j in range(1, 2 * k, 2):
dp[0][j] = -prices[0]
# 动态规划填表
for i in range(1, len(prices)):
for j in range(0, 2 * k - 1, 2):
# 计算买入的状态 dp[i][j + 1]
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i])
# 计算卖出的状态 dp[i][j + 2]
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i])
# 最后返回 dp[-1][2*k]，即最终状态最大利润
return dp[-1][2 * k]
二、力扣309. 最佳买卖股票时机含冷冻期
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例:
输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
这道题目是关于股票买卖的最佳时机问题，其中包含一个冷冻期的设定，即在卖出股票后的第二天无法买入股票。这使得问题的状态比普通的股票交易问题要复杂得多。
我们可以用动态规划来解决这个问题。根据问题的描述，可以将每一天的操作状态划分为以下四种：
- 状态一：持有股票，即 dp[i][0]。此状态可以是今天买入股票，或者之前买入股票后没有卖出，一直持有到今天。
- 状态二：不持有股票，且保持卖出后的状态（冷冻期已结束），即 dp[i][1]。此状态可以是前一天已经是该状态，或两天前卖出后进入冷冻期，今天冷冻期结束。
- 状态三：今天卖出股票，即 dp[i][2]。
- 状态四：今天为冷冻期状态，即 dp[i][3]。冷冻期是卖出股票后的第二天，无法买入股票。
状态转移方程
（1）持有股票状态（状态一，dp[i][0]）：
今天没有买入股票，延续前一天的持有状态：dp[i][0] = dp[i-1][0]
今天买入股票，有两种情况：
- 前一天处于冷冻期状态：dp[i][0] = dp[i-1][3] - prices[i]
- 前一天处于不持有股票且保持卖出后的状态：dp[i][0] = dp[i-1][1] - prices[i]
综合起来：dp[i][0] = max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i-1][1] - prices[i])
（2）不持有股票且保持卖出后的状态（状态二，dp[i][1]）：
今天没有操作，延续前一天的状态：dp[i][1] = dp[i-1][1]
今天从冷冻期恢复到正常状态：dp[i][1] = dp[i-1][3]
综合起来：dp[i][1] = max(dp[i-1][1], dp[i-1][3])
（3）今天卖出股票状态（状态三，dp[i][2]）：
昨天一定是持有股票状态：dp[i][2] = dp[i-1][0] + prices[i]
（4）冷冻期状态（状态四，dp[i][3]）：
昨天卖出股票：dp[i][3] = dp[i-1][2]
初始条件
状态一：第 0 天持有股票的状态，dp[0][0] = -prices[0]。
状态二、状态三、状态四：第 0 天不可能有卖出或冷冻期，因此 dp[0][1] = dp[0][2] = dp[0][3] = 0。
代码实现
from typing import List
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n == 0:
return 0
# 创建动态规划数组，4个状态分别表示持有股票、不持有股票且不处于冷冻期、不持有股票且当天卖出后处于冷冻期、不持有股票且处于冷冻期
dp = [[0] * 4 for _ in range(n)]
# 初始状态：第 0 天持有股票的最大利润为买入股票的价格
dp[0][0] = -prices[0]
for i in range(1, n):
# 持有股票状态
dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])
# 不持有股票且处于冷冻期的状态
dp[i][1] = max(dp[i-1][1], dp[i-1][3])
# 今天卖出股票的状态
dp[i][2] = dp[i-1][0] + prices[i]
# 冷冻期状态
dp[i][3] = dp[i-1][2]
# 返回最后一天不持有股票的最大利润
return max(dp[n-1][1], dp[n-1][2], dp[n-1][3])
三、力扣714. 买卖股票的最佳时机含手续费
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
这道题目是关于股票买卖的最佳时机问题，不过这里额外增加了交易的手续费限制。问题的目标是计算出在考虑每笔交易手续费的情况下，能够获得的最大利润。
状态定义
dp[i][0]：表示第 i 天持有股票的状态下，所能获得的最大现金（利润）。
dp[i][1]：表示第 i 天不持有股票的状态下，所能获得的最大现金（利润）。
状态转移方程
（1）持有股票状态 (dp[i][0])：
- 如果第 i-1 天已经持有股票，那么今天保持持有状态：dp[i][0] = dp[i-1][0]
- 如果第 i 天买入股票，那么今天的现金等于昨天不持有股票的现金减去今天买入股票的价格：dp[i][0] = dp[i-1][1] -
prices[i] - 取以上两者的最大值：dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
（2）不持有股票状态 (dp[i][1])：
- 如果第 i-1 天已经不持有股票，那么今天保持不持有状态：dp[i][1] = dp[i-1][1]
- 如果第 i 天卖出股票，那么今天的现金等于昨天持有股票的现金加上今天卖出股票的价格，并减去交易手续费：dp[i][1] =
dp[i-1][0] + prices[i] - fee - 取以上两者的最大值：dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
初始条件
第一天持有股票的最大利润：dp[0][0] = -prices[0]（即买入股票后的现金减少）。
第一天不持有股票的最大利润：dp[0][1] = 0（初始状态下不持有股票，现金为0）。
代码实现
from typing import List
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
n = len(prices)
if n == 0:
return 0
# 初始化 dp 数组，dp[i][0] 持有股票，dp[i][1] 不持有股票
dp = [[0] * 2 for _ in range(n)]
# 初始状态
dp[0][0] = -prices[0] # 第一天持有股票
dp[0][1] = 0 # 第一天不持有股票
for i in range(1, n):
# 第 i 天持有股票的状态
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
# 第 i 天不持有股票的状态
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
# 最后一天的最大利润应该是不持有股票的状态下的利润
return dp[-1][1]