引言

股票问题是dp问题中很重要的一类问题，其主要思想是每次分为持有股票和持有现金两个状态，这两个状态分别可以从前一天保持和当天改变得到。

基本方法 :

dp[i][0][k] 表示在第i天，持有现金的情况，且此时还可以进行的交易次数数k
dp[i][1][k] 表示在第i天，持有股票的情况，且此时还可以进行的交易次数数k

初始值设定：

一般情况下，我个人喜欢对dp进行padding，也就是构造n+1行2列的dp。
初始时，不可能持有股票，因此dp[0][1] = float('-inf')。而不持有股票时，收益为0dp[0][0] = 0。
对于转手次数，k = 0时，不可能发生交易。因此dp[i][0][0], dp[i][0][1] = 0, float('-inf')

转移方程：

每次进行转移时:
dp[i][0][k] = max(dp[i-1][0][k], dp[i-1][1][k]+prices[i])
dp[i][1][k] = max(dp[i-1][1][k], dp[i-1][0][k-1]-prices[i])
注意，是在买入时候，减少次数

需要冷却期的股票交易

冷冻期的问题需要额外多一个padding，同样可以利用初始值的float('-inf')表示了不可能的情况。

class Solution(object):def maxProfit(self, prices):# 这里对于0不持有股票和1持有股票设置了不同的初值，解决了很多初值问题## 第一个状态，持有股票应该是-price，不持有应该是0dp = [[0, float('-inf')] for _ in range(len(prices)+2)]for i in range(2,len(prices)+2):dp[i][0] = max(dp[i-1][1]+prices[i-2], dp[i-1][0])dp[i][1] = max(dp[i-2][0]-prices[i-2], dp[i-1][1])return dp[-1][0]

含有手续费

手续费的问题是最基础的问题，也就是售出价格稍微高一点。

class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:n = len(prices)dp = [[0, float('-inf')] for _ in range(n+1)]for i in range(1, n+1):dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1]-fee)dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1])return dp[-1][0]

限制了只能交易K次的交易

class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:n = len(prices)# 如果k>n/2其实已经失去了限制左右if k>n//2:return self.helper(prices)dp = [[[0, float('-inf')] for _ in range(n+1)]for _ in range(k+1)]for i in range(n+1):dp[0][i] = [0, float('-inf')]for j in range(1,k+1):    for i in range(1,n+1):dp[j][i][0] = max(dp[j][i-1][0], dp[j][i-1][1]+prices[i-1])dp[j][i][1] = max(dp[j][i-1][1], dp[j-1][i-1][0]-prices[i-1])return dp[k][-1][0]def helper(self, prices):n = len(prices)dp = [[0, float('-inf')] for _ in range(n+1)]for i in range(1,n+1):dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i-1])dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i-1])#print(dp)return dp[-1][0]