股票问题通解

2020-12-28

动态规划表设置

第一维是第i天，第二维是目前交易的次数k，第三维是当前是否持有股票dp[i][k][0]是不持有股票，dp[i][k][1]是持有股票

基准情况

1 2	dp[-1][k][0] = 0, dp[-1][k][1] = -Infinity dp[i][0][0] = 0, dp[i][0][1] = -Infinity

状态转移方程

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



注意到允许的最大交易次数是不变的，因为每次交易包含两次成对的操作，**买入**和**卖出**。只有**买入**操作会改变允许的最大交易次数。



1、对于状态转移方程中的```dp[i][k][0]```,第```i```天进行的操作只能是**休息**或**卖出**，因为在第```i```天结束时持有的股票数量是0. 


- ```dp[i-1][k][0]```是**休息**操作可以得到的最大收益
- ```dp[i-1][k][1]+pricepi[i]```是**卖出**操作可以得到的最大收益。


2、对于状态转移方程中的```dp[i][k][1]```,第i天进行的操作只能是**休息**或**买入**，因为在第```i```天结束时持有的股票数量是```1```. 

- ```dp[i-1][k][1]```是**休息**操作可以得到的最大收益
- ```dp[i-1][k-1][1]+price[i]```是**买入**操作可以得到的最大收益。

注意到允许的最大交易次数减少了一次，因为每次**买入**操作会使用一次交易。


为了得到最后一天结束时的最大收益，可以遍历股票价格数组，根据状态转移方程计算```dp[i][k][0]``` 和 ```dp[i][k][1]``` 的值。最终答案是 ```dp[n - 1][k][0]```，因为结束时持有 ```0``` 份股票的收益一定大于持有 ```1``` 份股票的收益。

----
<br>

# 当k=1时，即仅允许交易一次

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


所有的k都是1，即退化为

**基准情况**

dp[0][0] = 0;
dp[0][1] = -prices[0];

1	状态转移方程

dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i])
dp[i][1]=Math.max(dp[i-1][1],-price[i]);


```java
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
        }
        return dp[length - 1][0];
    }
}

当k为正无穷时，可以任意次交易

如果 k 为正无穷，则 k 和 k - 1 可以看成是相同的

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

基准情况

1 2	dp[0][0] = 0; dp[0][1] = -prices[0];

状态转移方程

1 2	dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+price[i]) dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-price[i]);

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

当k=2时，即仅允许交易两次

基准情况

dp[0][1][0] = 0;
dp[0][1][1] = -prices[0];
dp[0][2][0] = 0;
dp[0][2][1] = -prices[0];

状态转移方程

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

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][][] dp = new int[length][3][2];
        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        dp[0][2][0] = 0;
        dp[0][2][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][2][0] = Math.max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
            dp[i][2][1] = Math.max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
            dp[i][1][0] = Math.max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
            dp[i][1][1] = Math.max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]);
        }
        return dp[length - 1][2][0];
    }
}

当 0<= K <=price.length/2 时

一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。如果股票价格数组的长度为 n，则有收益的交易的数量最多为 $n / 2$（整数除法）。因此 k 的临界值是 $n / 2$。如果给定的 k 不小于临界值，即 $k >= n / 2$，则可以将 k 扩展为正无穷，此时问题等价于情况二。

可以写出时间复杂度为 $O(nk)$ 和空间复杂度为 $O(nk)$ 的解法。

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        if (k >= length / 2) {
            return maxProfit(prices);
        }
        int[][][] dp = new int[length][k + 1][2];
        for (int i = 1; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i < length; i++) {
            for (int j = k; j > 0; j--) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[length - 1][k][0];
    }

    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

k为正无穷但有冷却时间

但是在有「冷却时间」的情况下，如果在第 i - 1 天卖出了股票，就不能在第 i 天买入股票。因此，如果要在第 i 天买入股票，第二个状态转移方程中就不能使用dp[i - 1][k][0]，而应该使用 dp[i - 2][k][0]。状态转移方程中的别的项保持不变，新的状态转移方程如下：

1 2	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 - 2][k][0] - prices[i])

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);               //今天没有持有股票=（昨天没有持有股票）和（昨天持有股票，今天卖出）
            dp[i][1] = Math.max(dp[i - 1][1], (i >= 2 ? dp[i - 2][0] : 0) - prices[i]);//今天持有股票=（昨天持有股票）和（前天没有持有股票今天买入）
        }
        return dp[length - 1][0];
    }
}

k为正无穷但有手续费

由于需要对每次交易付手续费，因此在每次买入或卖出股票之后的收益需要扣除手续费，新的状态转移方程有两种表示方法。

第一种表示方法，在每次买入股票时扣除手续费：

1 2	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][0] - prices[i] - fee)

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0] - fee;
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
        }
        return dp[length - 1][0];
    }
}

第二种表示方法，在每次卖出股票时扣除手续费：

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

class Solution {
    public int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        int[][] dp = new int[length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[length - 1][0];
    }
}

参考文献

作者：Storm股票问题系列通解（转载翻译）

作者：Storm
链接：https://leetcode-cn.com/circle/article/qiAgHn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。