学习资料：https://programmercarl.com/0188.买卖股票的最佳时机IV.html#算法公开课
动态规划之股票系列（2）
主要是要分持股状态来讨论各种情况，并由前一天的情况来讨论今天的金额
学习记录：
188.买卖股票的最佳时机IV（相当于2k+1维度）
点击查看代码
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
# 跟只能买卖两次异曲同工
length = len(prices)
if length == 0:
return 0
# 构造dp为j维数组 dp[i][j]代表第i天的状态为j
dp = [[0]*(2*k+1) for _ in range(length)]
# 初始化，这里对第1天的各种卖出状态进行初始化
for j in range(1, 2*k, 2):
# j状态，如0代表无操作，1代表第一次持股状态，2代表第一次不持股状态……
dp[0][j] = -prices[0] # 只要是1、3、5等状态就是持股状态，对于第一天而言，就是把钱花出去的状态，没有任何盈利
# 开始遍历
for i in range(1, length):
for j in range(0, 2*k-1, 2):
# 递推公式，第i天的状态可以分为持股j+1和不持股j+2得到
dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j]-prices[i])
dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1]+prices[i])
return dp[-1][2*k]
309.最佳买卖股票时机含冷冻期（要考虑今天卖和冷冻期和不持股和持股四种状态）
点击查看代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 设置四个状态分析
# 0：持股状态；1：不持股状态（不是今天卖也不是冷冻期）；2：今天卖出股票；3：冷冻期
# 构造dp数组
length = len(prices)
dp = [[0]*4 for _ in range(length)]
# 初始化，第一天的各种情况
dp[0][0] = -prices[0] # 第一天就买股
dp[0][1] = 0 # 是不正常的状态，需要根据递推公式来确定设置为多少，可以举例判断
dp[0][2] = 0
dp[0][3] = 0
# 开始遍历
for i in range(1, length):
# 若今天持股则昨天有三种可能状态：昨天持股，昨天不持股今天买入，昨天冷冻期今天买入（难点：昨天不可能卖出，不然今天冷冻买不了）
dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][3])-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[-1][1], dp[-1][2],dp[-1][3]) # 要最大利润，最后一天必为各种无股状态
714.买卖股票的最佳时机含手续费（只考虑两种状态持股或不持股，只是卖的时候要多加个手续费）
点击查看代码
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
length = len(prices)
# 几种状态：0持股，1不持股
dp = [[0]*2 for _ in range(length)]
dp[0][0] = -prices[0] # 买入股票不要手续费，要卖出才是一次完整的交易
for i in range(1, length):
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[-1][1], dp[-1][0])
PS：今天下了很小的雨，又是面试的一天，爽，吃美食，好困终于要到周末了
标签：持股,状态,买卖,股票,length,最佳时机,max,prices,dp From： https://www.cnblogs.com/tristan241001/p/18537249