DP-股票买卖问题_1302:股票买卖

股票买卖问题

股票买卖问题是一类十分经典的动态规划问题，问题描述如下：

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

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

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
1
2
3

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
1
2
3
4

上面就是最基本的股票买卖问题，还有其他几个变种题，原理都是一样的，掌握最基本的原理，其他都是小case。

下面分析怎么利用动态规划的思想求解上面的问题：

1、三种状态：天数、允许交易的最大次数、当前的股票持有状态（不妨用 1 表示持有，0 表示没有持有）。

三种状态定义dp数组：

dp[i][k][2]
i为当前天数
k 为当前的最多交易数
举例：
`dp[3][2][1]` 的含义就是：今天是第三天，我现在手上持有着股票，至今最多可以进行 2 次交易。
1
2
3
4
5

3、三种选择：买入、卖出、无操作
我们用 buy, sell, rest 表示这三种选择。但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。

由三种选择可以写出下面的状态转移方程（核心）

2、base case

dp[-1][...][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。

dp[-1][...][1] = -infinity
解释：还没开始的时候，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

dp[...][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。

dp[...][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

4、最终答案： dp[ n - 1 ] [ K] [0]
最后一天，最多允许 K 次交易，手上股票交易完 的情况下，获得的利润最大。

以上就是对股票买卖问题的理论分析，下面就是leetcode上股票买卖问题全家桶了

第一题，k = 1

买卖股票的最佳时机

标准写法

思路：
直接套状态转移方程，根据 base case，可以做一些化简：

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

由于dp[i-1][0][0] = 0 因为没法交易时肯定利润为0，所以省略dp[i-1][0][0]得到：

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

可以发现上面的 k 取值都是 1，没有取值为0的情况，那么一个常数是可以直接省略的，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 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])
1
2

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        //base case 第一天
        dp[0][0]=0;
        dp[0][1]=-prices[0]; 
        for (int i = 1; i < n; i++) { //从第2天开始往后
            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[n - 1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

状态压缩（重点）

注意一下状态转移方程，新状态只和相邻的一个状态有关，所以不用定义dp 数组记录结果，只需要一个变量储存相邻的那个状态就足够了，这样可以把空间复杂度降到 O(1)

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        //第一天
        int dp0=0,dp1=-prices[0]; 
        for (int i = 1; i < n; i++) { //从第2天开始往后
            dp0=Math.max(dp0,dp1+prices[i]);
            dp1=Math.max(dp1,-prices[i]);
        }
        return dp0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

第二题，k = +infinity

买卖股票的最佳时机 II

标准写法

如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。数组中的 k 已经不会改变了，也就是说不需要记录 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])
1
2

代码：

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][]dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for (int i =1; i < n; 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[n-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

状态压缩

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int dpNon=0,dpGet=-prices[0];
        for(int i=1;i<n;i++){
            int temp=dpNon; //将dpNon保存下来，更新dpGet时需要用到，不然在第1步时dpNon被更新了
            dpNon=Math.max(dpNon,dpGet+prices[i]);//1
            dpGet=Math.max(dpGet,temp-prices[i]);
        }
        return dpNon;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

第四题，k = any integer

买卖股票的最佳时机 IV

本题就是一开始分析的最经典的股票买卖问题，k取任意正整数

注意： 当k 值非常大时，会出现一个超内存的错误，现在想想，交易次数 k 最多有多大呢？

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

直接把之前的代码重用：

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n=prices.length;
        //采用k无限次的方法进行优化
        if (k>n/2){
            return maxProfit_inf(prices);
        }
        int[][][]dp=new int[n][k+1][2];
        for (int i = 0; i <n; i++) {
            for (int j = 1; j <= k; j++) {
            // base case 
                if (i==0){
                    dp[i][j][0]=0;
                    dp[i][j][1]=-prices[i];
                    continue;
                }
                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[n-1][k][0];
    }
    private int maxProfit_inf(int[] prices) {
        int dp0=0,dp1=Integer.MIN_VALUE; //prices数组长度可能为0，不能初始化为-prices[0];
        for (int i = 0; i < prices.length; i++) {
            int temp=dp0;
            dp0=Math.max(dp0,dp1+prices[i]);
            dp1=Math.max(dp1,temp-prices[i]);
        }
        return dp0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

第五题，k = +infinity with cooldown

添加链接描述
每次 sell 之后要等一天才能继续交易。只要把这个特点融入上一题的状态转移方程即可：

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])
解释：第 i 天选择 buy 的时候，最晚 i-2天需要sell掉，所以从dp[i-2][0]的状态转移过来，而不是dp[i-1][0] 。
1
2
3

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if(n<2){
            return 0;
        }
        int[][]dp=new int[n][2];
        //第一天
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        //第二天
        dp[1][0]=Math.max(0,prices[1]-prices[0]); //可能没买，可能第0买第1天卖
        dp[1][1]= - Math.min(prices[0],prices[1]);//选择价格最低的那天买入
        for (int i =2; i < n; 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-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

由于需要记录前两天的值，所以不方便使用状态压缩。
c++：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n<2){
            return 0;
        }
        vector<vector<int>>dp(n,vector<int>(2));
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        dp[1][0]=max(0,prices[1]-prices[0]);
        dp[1][1]=-min(prices[0],prices[1]);
        for(int i=2;i<n;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-2][0]-prices[i]);
        }
        return dp[n-1][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第六题，k = +infinity with fee

买卖股票的最佳时机含手续费
每次交易要支付手续费，只要把手续费从利润中减去即可，买的时候缴纳手续费或者卖的时候缴纳都行，但是要保证统一

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        if(n<2){
            return 0;
        }
        int[][]dp=new int[n][2];
        dp[0][0]=0;
        dp[0][1]=-(prices[0]+fee); //买的时候缴纳手续费

        for (int i = 1; i < n; 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[n-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

状态压缩：

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int has=-prices[0],non=0;
        for(int i=1;i<prices.length;i++){
            has=Math.max(has,non-prices[i]);
            non=Math.max(non,has+prices[i]-fee);//卖的时候缴纳手续费
        }
        return non;
    }
}
1
2
3
4
5
6
7
8
9
10

总结

三个状态：当前天，当前可进行的操作次数k，当前是否持有股票
k=1时或∞时， k可以省略，且可以状态压缩
其他情况下k不能省，且不能状态压缩

base case ：
第一天是否持有股票

dp[0][k][0] = 0 //不持有
dp[0][k][1] = -price[0] //在第一天如果持有股票的话，一定是在第一天买了股票
1
2