DP-股票买卖问题

股票买卖问题

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

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

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

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

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

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

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

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

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

三种状态定义dp数组：

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

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
解释：不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

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

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

可以发现上面的 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])

代码：

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];}
}

状态压缩（重点）

注意一下状态转移方程，新状态只和相邻的一个状态有关，所以不用定义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;}
}

第二题，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])

代码：

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];}
}

状态压缩

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]);//1dpGet=Math.max(dpGet,temp-prices[i]);}return dpNon;}
}

第四题，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;}
}

第五题，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] 。

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];}
}

由于需要记录前两天的值，所以不方便使用状态压缩。
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];}
};

第六题，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];}
}

状态压缩：

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;}
}

总结

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

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

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