详解股票买卖算法的最优解(一)
详解股票买卖算法的最优解(一)
前言
今天王子与大家分享的是LeeCode上有关如何买卖股票获取最高利润的题目。
主要用的技巧是“状态机”，那么什么是“状态机”呢？没听过的小伙伴会觉得它很高大尚，但今天我们讨论过后，你会发现其实它就是那么回事。
接下来，我们就以下边的题目为基础，讲解一下“状态机”是什么。
请看题：
看完题目后是不是觉得无从下手呢，没关系，接下来我们进入正题。
穷举框架
首先我们会想到，要解决这个问题需要怎么进行穷举，获取出最大的利润呢？要穷举的对象又是什么呢？
既然我们选择了状态机，那么要穷举的对象就是是状态，穷举状态的一种框架就是下边的模式:
for 状态1 in 状态1的所有取值
for 状态2 in 状态2的所有取值
for ...
dp[状态1][状态2][...] = 择优（选择1，选择2，...）具体到我们的题目，分析可以知道我们每天都有三种选择：买入、卖出、卧倒不动，我们用buy、sell、rest表示这三种选择。
在此基础上，我们再次分析，可以知道每天是不能随意选择这三种选择的，它的选择是有限制条件的。
sell必须要在buy之后，buy又必须在sell之后（除了第一次）。而对于rest又有两种情况，如果是在buy之后rest，那么目前就是持仓状态，如果是在sell之后rest，那么目前就是空仓状态。而且我们还有一个买入次数K的限制，所以我们的buy是有限制的，buy<k, k>0。
分析题目，这个问题有三种状态,第一个是天数，第二是允许交易的最大次数k,第三个是当前的持有状态（空仓还是持仓，我们假设空仓为0，持仓为1）
看起来还可以理解吧，那么如何穷举呢？
我们用一个三维数组dp就可以存储这几种状态的全部组合，然后就可以用for循环完成穷举，如下：
dp[i][k][0 or 1]
0<=i<=n-1,1<=k<=K
//n为天数，K为最多交易次数，全部穷举如下
for 0<=i<n;
for 1<=k<=K;
for s in {0,1};
dp[i][k][s] = max(buy,sell,rest)如果上边的表达式还是没有看明白，那么我们可以用大白话描述出每一个状态的含义，比如说dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今进行 3 次交易。这样就更容易理解了吧。
我们想要的最大利润值一定是 dp[n - 1][k][0]，也就是最后一天，交易了k次，空仓状态。为什么说是空仓状态利润最大呢，可以这么理解，假设我们手上一共就这么多钱用于买卖股票，不考虑利润的情况下，如果买入股票变为持仓状态，可以看成是我们的总资金减去了买入的资金，实际上我们的资金是变少的，而卖出变为空仓状态，可以看成是我们把买入的资金又以不同的价格卖了出去，此时我们的总资金才真的增加了钱数，对于我们的总资金来说才算真正的盈利了。这其实就是我们平时理财的一个道理，如果买入了股票或基金，只要不卖出，你就不会真正的盈利，同样也不会真正的亏损，好了这是题外话，之后会有理财专辑专门谈谈理财，我们回归正题。
状态转移框架
我们知道了有多少状态，有多少选择，那么现在我们就开始考虑每种状态有哪种选择，他们之间如何组合。
三种选择buy、sell、rest是只与持有状态相关的，所以可以画出一个状态转移图如下：
通过这个图我们可以清楚的看到0和1之间是如何因为选择而转换的。可以写出状态转移方程如下：
dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])
max( 选择rest, 选择sell )
解释：今天没有持有股票有两种情况
昨天没有持有，今天没有操作，所以今天没有持有
昨天持有股票，今天卖出操作，所以今天没有持有
dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i])
max( 选择rest, 选择buyl )
解释：今天持有股票有两种情况
昨天持有股票，今天没有操作，所以今天持有股票
昨天没有持有，今天买入操作，所以今天持有股票转移方程中的解释应该很清楚了，如果buy就从总钱数里减去prices[i]，如果sell就给总钱数加上prices[i]。那么今天的最大利润就是在这两种选择中选取总钱数最大的那种情况。而且要保证交易次数的限制，buy了一次k就增加1，保证k<K。
现在我们已经把解题的核心部分，状态转移方程写完了，那么对于题目其实就是套用框架了，不过在套用之前，我们先把一些特殊情况考虑进去。
dp[-1][k][0] = 0;
// 因为i>0，所以i=-1代表还没开始，利润为0
dp[-1][k][1] = 不存在;
// 还没开始是不可能持有股票的
dp[i][0][0] = 0;
// k=0代表还没交易过，利润当然是0
dp[i][0][1] = 不存在;
// k=0代表还没交易过，不可能持有股票解决题目
第一题：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]);
// 因为dp[i-1][0][0]=0
// 可以发现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]);同时我们还要考虑当i=0的时候，情况特殊，所以我们可以单独设置变量存储特殊情况
翻译成最终代码如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,-prices[i]);
}
return dp_i_0;
}相信小伙伴们前边的内容理解清楚后，最终的代码是能够看懂的，我们继续看下一题。
第二题，k=+infinity，及不限制交易次数
如果k=+infinity，那么就可以认为k-1=k，所以可以引入改写框架如下：
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]);
// 可以发现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]);直接翻译成代码如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]);
}
return dp_i_0;
} 第三题，k=+infinity ,而且带有冷冻期
解释一下题目，就是，卖出股票后，你无法在第二天买入股票 (即冷冻期为 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-2][0]-prices[i]);
// 第i天选择buy的时候，要从i-2的状态转移（冷冻期1天）直接翻译成代码如下：
public int maxProfit(int[] prices) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
int dp_pre_0=0;//代表dp[i-2][0]
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,dp_pre_0-prices[i]);
dp_pre_0=temp;
}
return dp_i_0;
} 第四题，k=+infinity,带手续费
手续费题目中这样描述：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
那么状态转移方程中，我们每次卖出的时候，把手续费减掉就可以了，如下：
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);
// fee代表手续费，两个式子里随便一个减掉一次就可以了，可以看成是买入的时候交手续费或者卖出的时候交手续费直接翻译成代码如下：
public int maxProfit(int[] prices,int fee) {
int n=prices.length;
int dp_i_0=0,dp_i_1=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int temp=dp_i_0;
dp_i_0=Math.max(dp_i_0,dp_i_1+prices[i]);
dp_i_1=Math.max(dp_i_1,temp-prices[i]-fee);
}
return dp_i_0;
} 总结
好了，看到这里以上4道关于股票买卖的算法题我们就完美解决了，小伙伴们看懂了吗，希望大家仔细思考解题思路，能实际运用这套框架哦，这是关于股票买卖算法的第一篇文章，后续会有补充内容，对剩下比较复杂的题目提供解题方法，欢迎阅读我的下一篇文章，一起研究算法吧。
往期文章推荐：
中间件专辑：
算法专辑：
腾讯云开发者
