复盘股票问题

通过leetcode上的几道经典的股票问题，我们由浅入深地认识到动态规划的精妙之处，下面我们来复盘一下股票问题的解题思路，看我们是如何抽丝剥茧，一步一步地逼近正确思路，迎来柳暗花明的。

首先还是老生常谈的问题：遇到动态规划问题，首先思考【状态】和【选择】的问题。
在股票系列问题中，最初拿到题目时不要慌，再复杂的问题都是有套路可循的，若要用动态规划，我们首先要思考其【状态】，再说的通俗一点就是【变量】，看问题中哪些量是变化的，在此题中是“天数” “交易次数” “股票的持有状态”。那么怎样寻找状态转移呢？此时我们要知道所谓【状态转移】是和【选择】形影不离的，做出【选择】后自然迎来【状态变化】，那么在此问题中【选择】就是“买入”或“卖出”股票或者“观望（不买也不卖）”
下面贴上顺藤摸瓜的思路：在这里插入图片描述

顺着这样的思路便可将股票系列问题一网打尽。

下面再贴上股票系列问题（K=2）的代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size(),K=2;if(n==0)return 0;vector<vector<vector<int> > >dp(n,vector<vector<int> >((K+1),vector<int>(2)));for(int i=0;i<n;i++){for(int k=2;k>=1;k--){if(i-1==-1){dp[i][k][0]=0;dp[i][k][1]=-prices[i];continue;}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]);//这里着重说一下dp[i-1][k-1][0]是怎么来的，注意我们在写代码之前//一定要清楚dp数组的含义，这里我们的dp[i][K][0]是指第i天，//总共交易次数为K且未持有股票，那么因为我们定义买入时操作算一次//交易，所以在dp[i][k][1]=max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]);//这次状态变化中，这一天的持有股票状态若由前一天未持有而今天//又买入转化而来，则说明今天一定是进行了一次交易，而到今天为止//允许的最大交易次数为K，那么昨天允许的最大交易次数就一定为k-1（因为今天进行了一次交易，所以必须必昨天多一次交易机会）}}return dp[n-1][K][0];}
};