有限状态机的动态规划

参照UML的状态机图，我们可以枚举出一个应用中所有的状态及其转换条件，和我们的动态规划的状态转移方程有异曲同工之妙。见下面例题：

LC122 买卖股票的最佳时机Ⅱ

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

示例

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

题解

这是力扣在动态规划方面的经典例题，对于这道题来说，总共有四种状态转换的条件：

1. 已经持有股票，并且卖出
2. 已经持有股票发现卖出亏本，不卖
3. 没有持有股票，买入
4. 没有持有股票买入亏本，不买

容易列举状态转移方程：

代码就很容易写出来了：

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // dp[i][0]代表第i天不持有股票的最大利润
        // dp[i][1]代表第i天持有股票的最大利润
        int[][] dp = new int[len][2];
        // 第0天不买
        dp[0][0] = 0;
        // 第0天买股票
        dp[0][1] = -prices[0];

        for (int i = 1; i < len; i++) {
            // 第i天卖出, 获得的最大利润
            dp[i][0] = Math.max(prices[i] + dp[i - 1][1], dp[i - 1][0]);
            // 第i天买入, 获得的最大利润
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][0];
    }
}

我们发现dp数组只有i和i-1两个在用，所以可以压缩一下，只记录前一个状态量。

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int dp1 = 0, dp2 = -prices[0];

        for (int i = 1; i < len; i++) {
            // 第i天卖出, 获得的最大利润
            dp1 = Math.max(dp2 + prices[i], dp1);
            // 第i天买入, 获得的最大利润
            dp2 = Math.max(dp1 - prices[i], dp2);
        }
        return dp1;
    }
}

LC123 买卖股票的最佳时机 III 状态增加

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

题解

像这种状态增多的又应该怎么办了，其实原理还是一样的，我们先列举所有的状态转移条件：

1. 第i天股票上市，可以选择买还是不买第一支股票，买则进入2，否则继续1
2. 第i天是否出售第一支股票，出售进入3，否则继续2
3. 第i天股票上市，可以选择买还是不买第二只股票，买则进入4，否则继续3
4. 第i天是否出售第二支股票，出售进入终止状态，否则继续4

代码当然也非常简单了：

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null || prices.length==0) {
            return 0;
        }
        int n = prices.length;
        //定义5种状态，并初始化第一天的状态
        int dp1 = -prices[0];
        int dp2 = 0;
        int dp3 = -prices[0];
        int dp4 = 0;
        for(int i=1;i<n;++i) {
            //处理第一次买入、第一次卖出
            dp1 = Math.max(dp1,-prices[i]);
            dp2 = Math.max(dp2,dp1+prices[i]);
            //处理第二次买入、第二次卖出
            dp3 = Math.max(dp3,dp2-prices[i]);
            dp4 = Math.max(dp4,dp3+prices[i]);
        }
        //返回最大值
        return dp4;
    }
}

我之前还做过一个更加有难度的状态机题，当时云里雾里，现在有着更加深刻的理解了，详细参见：监控二叉树