[leetcode刷题笔记]动态规划——买卖股票问题

面试时遇到股票买卖问题（k次交易），因为之前掌握不熟没做出来打击还是挺大的，于是狂刷这类问题，对动态规划，特别是画状态转换图，并根据图写状态转移方程了解的更加深入。

买卖股票的最佳时机

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

买卖股票的最佳时机 II

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

买卖股票的最佳时机 III

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

买卖股票的最佳时机 IV

设计一个算法来计算你所能获取的最大利润。你最多可以完成k 笔交易。

最佳买卖股票时机含冷冻期

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

买卖股票的最佳时机含手续费

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

股票买卖问题的状态转移图如图所示，有两个状态分别代表买入和卖出股票后，同时也可选择持有不进行状态转移操作。

使用dp[i][k][0]和dp[i][k][1]表示状态，其中dp[i][k][0]表示第i天最多进行k次交易时卖出后的利润，dp[i][k][1]表示第i天最多进行k次交易时买入后的利润。

初始条件

dp[i][0][0] = 0 #没有进行任何买入，当前持有利润为0
dp[i][0][1] = -prices[0] #进行一次卖出，当前利润为 -prices[0]

根据状态转移图，可写出动态转移方程

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[I]) 
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[I])

特别地，当k=1时(买卖股票的最佳时机)，dp[i-1][k-1][0] === 0，故可简化为

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1],  - prices[I])

当k=float('inf')时(买卖股票的最佳时机 II)，k=k-1，故可简化为

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])

下面两道题是在k无限次时增加条件，因此对上述方程进行修改。

含冷冻期问题(最佳买卖股票时机含冷冻期)因为增加了1天的冷冻时间，在卖出后（状态1）无法在第二天进行买入（买入），因此买入时非i-1天而是i-2天，状态转移方程为：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[I])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[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] - fee)

当k=2时(买卖股票的最佳时机 III)，可使用一般形式的状态转移方程解决。

一般情况下（买卖股票的最佳时机 IV）的完整代码如下：

class Solution:
def maxProfit(self,k: int, prices: List[int]) -> int:

    if not prices:
        return 0

    dp = [[[0] * 2  for _ in range(k+1) ]for _ in range(len(prices))]

    for k in range(1,k+1):
        dp[0][k][0] = 0
        dp[0][k][1] = -prices[0]

    for i in range(1,len(prices)):
        for k in range(1,k+1):
            dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[I])
            dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[I])
    
    return dp[-1][k][0]

在本题测试用例中有一个较大的k导致程序超时，当k较大时（k > len(prices)//2），此时说明每天都在买入或卖出操作，用贪心算法将这一特殊情况处理掉。

    if k > len(prices)//2:
        maxnum = 0
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                maxnum += prices[i] - prices[i-1]
        return maxnum