股票买卖系列-通用解法

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

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

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

解题思路

动态规划有三要素：阶段、状态和决策。

阶段：

把一个问题的过程，恰当地分为若干个相互联系的阶段，以便于按一定的次序去求解。描述阶段的变量称为阶段变量。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。

状态：

表示每个阶段开始所处的自然状况或客观条件。通常一个阶段有若干个状态（也可能只有一个状态），描述过程状态的变量称为状态变量。

决策：

表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策。

一般流程：

划分阶段 -> 正确选择状态变量 -> 确定状态转移方程

-> 确定阶段指标函数和最优指标函数，建立动态规划基本方程。

代码

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    int dp[100010][3][2];

    int maxProfit(vector<int>& prices) {
        //状态机dp
        //阶段----当前是第i天，也就是时间。
        //状态：剩余交易次数、股票持有状态下的股票收益
        //决策：卖出股票、啥也不做、买入股票
        int n = prices.size();
        int k = 2;
        //base
        for (int k = 0; k <= 2; k++) {
            dp[0][k][0] = 0;
            dp[0][k][1] = -inf;
        }

        for (int i = 0; i <= n; ++i) {
            dp[i][0][0] = 0;
            dp[i][0][1] = -inf;
        }
        
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= 2; k++) {
                              //前一天没有股票；昨天有股票，今天卖出；
                dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i - 1]);
                                //前一天有股票；昨天没有股票，今天买入
                dp[i][k][1] =  max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i - 1]); 
            }
        }

        return dp[n][2][0];
    }
};