对于股票问题集合的总结（多状态状态机DP）

这篇文章作为股票问题的集合，篇幅过长，故而不放示例进来，如需查看完整题目，请移步leetcode。

题目1（买卖股票的最佳时机-leetcode-121）

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

解题思路

这道题是问题的开端，这里的最大利润的思想会延续到后面的所有题之中，这里的本意很好理解，就是我们需要找到一个低点和高点，进行买入和卖出，寻求利润的最大点，这里暗藏的条件是：
1.同时只能持有一支股票。
2.不能在同一天进行买入和卖出。
3.买入卖出无手续费。
4.买入卖出无冷静期。
但就这题而言，我们就可以显然得到一个暴力解：维护两个指针，使用双重循环去找到一个maxProfit=max(maxProfit,price[j]-price[i])。那么我们显然不能使用这个时间复杂度到了O(n^2)的方案了，这样一点都不优雅，我们就思考能不能只遍历一次，就得到答案。那么显然是可以的，我们只需要引入一个minPrice的变量，通过一次遍历，每次满足条件就更新minPrice，在循环末进行max就行了。

代码实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans=0;
        int minp=INT_MAX;
        for(int i=0;i<prices.size();i++){
            if(minp>prices[i]){
                minp=prices[i];
            }
            ans=max(ans,prices[i]-minp);
        }
        return ans;
    }
};

题目2（买卖股票的最佳时机II-leetcode-122）

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。
返回 你能获得的 最大 利润 。

解题思路

这一题开始就开始了状态机dp了，这个题包含了四种不同情况，我们先假定1是持有股票，0是不持有股票，那么第i天的总利润实际上的公式可以写成
dfs[i]=dfs[i-1]+prices[i]
这里就包含了四种情况：
1.第i天我本身没有股票，要购入股票，那么这个时候实际上是-prices[i]，持有状态从1变成0。2.第i天我本身持有股票，我现在要卖出股票，那么这个时候实际上是+princes[i]，持有状态从0变成1。
3.我本身没有股票，但是我什么也没做，持有状态还是保持1。
4.我本身有股票，但是我什么也不做，持有状态还是保持0。
这个时候我就可以写出一个递推方程了,这里还要注意最初状态不能持有股票，因为显然我们最开始是没有股票的。但是简单的普通递归我们又容易超时，因为太多我们已经算过的递归值被重复计算了，所以我们需要一个记忆数组memo来存储这个状态机的状态。
这里暗藏的条件是：
1.同时只能持有一支股票。
2.能在同一天进行买入和卖出。
3.买入卖出无手续费。
4.买入卖出无冷静期。

图片示意

代码实现

class Solution {
private:
    vector<array<int,2>>memo;
public:
    int dfs(int i,bool hold,vector<int>&prices){
        
        int ans;
        if (i<0&&hold==0){
            return 0;
        }//当i递归到起点时，且不持有股票，显然利润是0.
        if (i<0&&hold==1){
            return INT_MIN;
        }//当i递归到起点时，且持有股票，和题意相悖，显然不存在，故而用INT_MIN进行处理，INT_MIN用min函数进行处理
        if(memo[i][hold]!=INT_MIN){
            return memo[i][hold];//如果算过就直接返回算过的答案
        }
        if(hold==0){
            ans=max(dfs(i-1,0,prices),dfs(i-1,1,prices)+prices[i]);//第i天未持有
        }else{
            ans=max(dfs(i-1,1,prices),dfs(i-1,0,prices)-prices[i]);//第i天持有
        }
        memo[i][hold]=ans;
        return ans;
    }
    int maxProfit(vector<int>& prices) {
        memo.assign(prices.size(),array<int,2>{INT_MIN,INT_MIN});
        int ans=dfs(prices.size()-1,0,prices);
        return ans;
    }
};

题目3（买卖股票的最佳时机III-leetcode-123）

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路

这道题的解决方案实际上承袭了II的思路，只不过有个地方需要考虑，它引入了一个至多交易次数，所以我们只需要再引入一个j作为一个次数的衡量基准就行了，我们在这里把j也纳入我们的递归方程里面，因为这个j本身就是一个约束状态，我们可以算出在每个约束状态下的利润，再求出最大值。这里我们需要注意的是：每一天都有一个这样的表
| 最多允许卖出 j 次 | 不持有 hold = 0 | 持有 hold = 1 |
| —- | —- | —- |
| j = 0 | memo[i][0][0] | memo[i][0][1] |
| j = 1 | memo[i][1][0] | memo[i][1][1] |
| j = 2 | memo[i][2][0] | memo[i][2][1] |

我们需要用一个vector把他们包成一个数组，同时上面这个表格本身也是一个vector<array<int,2>>的一个数组，同时，买入和卖出这两个动作构成一个交易，所以在j变动的时候，只需要动一次就行。在这里，我们将买入作为一次交易完成的变动。

图片示意

这里暗藏的条件是：
1.同时只能持有一支股票。
2.有交易次数限制。
3.买入卖出无手续费。
4.买入卖出无冷静期。

代码示例

class Solution {
private:
    vector<vector<array<int,2>>>memo;
public:
    int dfs(int i,int j,bool hold,vector<int>&prices){
        if (j<0){
            return INT_MIN;
        }
        int ans;
        if (i<0&&hold==0){
            return 0;
        }
        if (i<0&&hold==1){
            return INT_MIN;
        }
        if(memo[i][j][hold]!=INT_MIN){
            return memo[i][j][hold];
        }
        if(hold==0){
            ans=max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)+prices[i]);
        }else{
            ans=max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);
        }
        memo[i][j][hold]=ans;
        return ans;
    }
    int maxProfit(vector<int>& prices) {
        memo.assign(prices.size(),vector<array<int, 2>>(3, array<int, 2>{INT_MIN, INT_MIN}));
        int ans=dfs(prices.size()-1,2,0,prices);
        return ans;
    }
};

题目4（买卖股票的最佳时机IV-leetcode-188）

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解题思路

那这道题就是III的思路了，直接在main函数里面把2改成k就行了。

代码示例

class Solution {
private:
    vector<vector<array<int,2>>>memo;
public:
    int dfs(int i,int j,bool hold,vector<int>&prices){
        if (j<0){
            return INT_MIN;
        }
        int ans;
        if (i<0&&hold==0){
            return 0;
        }
        if (i<0&&hold==1){
            return INT_MIN;
        }
        if(memo[i][j][hold]!=INT_MIN){
            return memo[i][j][hold];
        }
        if(hold==0){
            ans=max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)+prices[i]);
        }else{
            ans=max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);
        }
        memo[i][j][hold]=ans;
        return ans;
    }
    int maxProfit(int k, vector<int>& prices) {
        memo.assign(prices.size(),vector<array<int, 2>>(k+1, array<int, 2>{INT_MIN, INT_MIN}));
        int ans=dfs(prices.size()-1,k,0,prices);
        return ans;
    }
};

易错点

要牢牢记住状态的变化