状态转移方程

参考labuladong算法小抄。
实质：对所有状态进行枚举

base case：
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity

状态转移方程：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

1. 只能交易一次 k=1

说明k对结果没有影响，状态转移方程变成：

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

base case:
dp[-1][0],dp[-1][1] = 0,-float('inf')

代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = collections.defaultdict(dict)
        dp[-1][0],dp[-1][1]= 0, -float('inf')

        for i in range(0,n):
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
            dp[i][1] = max(dp[i-1][1],-prices[i])
        
        return dp[n-1][0] # 这里注意最后返回结果是dp[n-1][0]，没有股票在手里肯定比有股票在手里赚的前多

python写法中这里二维数组用的是dict，也可以用list

2. 可以交易任意次数(k=infinity)

k为正无穷，则可以认为k和k-1是一样的，k对结果没有影响.

状态转移方程变为：

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

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = collections.defaultdict(dict)
        dp[-1][0],dp[-1][1]= 0, -float('inf')

        for i in range(0,n):
            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])
        
        return dp[n-1][0]

3. 最多可以交易K次

一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k = +infinity。这种情况是之前解决过的。

状态转移方程为原始转移方程：

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

代码：

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

        def maxProfit_k_inf(prices):
            n = len(prices)
            dp = collections.defaultdict(dict)
            dp[-1][0],dp[-1][1]= 0, -float('inf')

            for i in range(0,n):
                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])
            
            return dp[n-1][0]

        # 现在有了k,所以需要有三个参数了
        n = len(prices)
        if n == 0 : return 0
        dp = [[[0]*2 for _ in range(k+1)] for _ in range(n)]

        for i in range(0,n):
            for ks in range(1,k+1):
                if i == 0:
                    dp[i][ks][0] = 0
                    dp[i][ks][1] = -prices[i]
                    continue
                dp[i][ks][0] = max( dp[i-1][ks][0] , dp[i-1][ks][1] + prices[i])
                dp[i][ks][1] = max( dp[i-1][ks][1] , dp[i-1][ks-1][0] - prices[i])
        
        return dp[n-1][k][0]

python实现的时候用三维数组，有两个注意点：

1. 创建的时候用两个for循环,第二个for循环要循环k+1次，因为我们要求第k次的值，k=0是用不到的

2. dp创建时，所有元素初始值都设置为 0

3. base case：i=0时，dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])=-prices[i]