前言

动态规划第一要点抓住所以抽象状态，定位结果属于那个状态 & 状态之间的转移关系。动态规划重点还是把大问题划分成相同性质但规模更小的之问题。

一、卖股票的最佳时机

二、哨兵机制 & 动态规划

1、哨兵记录

public int maxProfit(int[] prices) {
        // 第i天卖，需要知道左边最低股票值，需此时入手，才能获取最大利益。
        // 所以需要从左边遍历+变量记录最小值。
        int minPrice = prices[0];
        int maxProfit = 0;

        for(int i = 1;i < prices.length;i++){
            maxProfit = Math.max(maxProfit,prices[i] - minPrice);

            minPrice = prices[i] < minPrice ? prices[i] : minPrice;
        }
        return maxProfit;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

2、动态规划

public int maxProfit(int[] prices) {
        int f = -prices[0];// 第一天持有股票的收益，因为只有前后相邻状态有关，所以将一维降维变量。

        int maxProfit = 0;
        for(int i = 1;i < prices.length;i++){
            maxProfit = Math.max(maxProfit,f + prices[i]);// 把持有的股票卖了，看看是不是赚的更多。

            f = Math.max(f,-prices[i]);// 选择入手股票最低的价格，即更新第i天的最低股票价格。
        }
        return maxProfit;
    }
1
2
3
4
5
6
7
8
9
10
11

总结

1）用哨兵记录前面的最值，防止每次都去重复寻找，从而降低时间复杂度。

2）动态规划：问题分解成性质相同规模更小的子问题 & 分析抓住各种状态 & 状态转移 & 最终状态。

参考文献

[1] LeetCode 卖股票的最佳时机