动态规划入门（一）：股票买卖系列问题_股票购买动态规划

1 本文内容

• 动态规划专题，通过股票买卖问题学习一维、二维的动态规划算法以及滚动数组的空间优化。
• leetcode 121. 买卖股票的最佳时机【easy】
• leetcode 122. 买卖股票的最佳时机 II【medium】
• leetcode 123. 买卖股票的最佳时机 III【hard】
• leetcode 188. 买卖股票的最佳时机 IV【hard】
• leetcode 309. 最佳买卖股票时机含冷冻期【medium】
• leetcode 714. 买卖股票的最佳时机含手续费【medium】

2 买卖股票的最佳时机

2.1 题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

2.2 示例

输入：[7,1,5,3,6,4]

输出：5

输入：prices = [7,6,4,3,1]

输出：0

2.3 容易理解的动态规划解法

首先提炼题信息（1）我们从始至终只能进行一次交易；（2）只有买入和卖出两种操作可以改变我们的的利润。

分析上述信息我们发现：（1）从始至终只存在三种状态：未进行过股票交易、买入且持有股票、买入且但未持有股票（已经卖出）。（2）第i天处于何种状态及获得怎样的收益只取决于第i - 1天的状态和收益。

假设buy[i]表示第i天进入买入且持有股票状态能够取得的最大利润；sell[i]表示第i天进入买入但未持有股票（已经卖出）状态 能够取得的最大利润。

可以得到状态转移方程（1）：$$buy[i]=Math.max(buy[i-1],0-prices[i])$$
因为第i天处于买入且持有股票状态有两种情况，要么是第i - 1 天就已经处于该状态，所以利润不变；要么就是第i - 1天之前都未进行过股票交易，在第i天进行了买入操作，则利润为 0 - prices[i]。

也可以得到状态转移方程（2）：$$sell[i]=Math.max(sell[i-1],buy[i-1]+prices[i])$$
因为第i天处于买入但未持有股票（已经卖出）状态有两种情况，要么是第i - 1 天就已经处于该状态，所以利润变；要么之前处于买入且持有股票状态，今天进行卖出。

所以有：

class Solution {
   
    public int maxProfit(int[] prices) {
   
        int[] sell = new int[prices.length];
        int[] buy = new int[prices.length];
        buy[0] = - prices[0];
        for(int i = 1; i < prices.length; i++){
   
            buy[i] = Math.max(buy[i - 1], 0 - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[prices.length - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后返回sell[prices.length - 1];是因为获取最大利润的情况必然是股票已经卖出的状态。

2.4 空间优化的动态规划解法

上面我们已经分析过，第i天处于何种状态及获得怎样的收益只取决于第i - 1天的状态和收益，因此我们不需要记录除i - 1和i以外的任何一天的状态。以此可以将两个数组优化为四个常量：sellPrev, sellCur, buyPrev, sellCur。

解答为：

class Solution {
   
    public int maxProfit(int[] prices) {
   
        int buyPrev = -prices[0], sellPrev = 0;
        int buyCur = 0, sellCur = 0;
        for(int i = 1; i < prices.length; i++){
   
            buyCur = Math.max(buyPrev, - prices[i]);
            sellCur = Math.max(sellPrev, buyPrev + prices[i]);
            buyPrev = buyCur;
            sellPrev = sellCur;    
        }
        return sellCur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.5 性能分析

两种动态规划解法只进行了规模为prices.length的单层for循环迭代，因此时间复杂度都是O(n)。
第一种解法开了2个大小为prices.length的数组，因此空间复杂度为O(n);第二种解法将空间优化为常量，因此空间复杂度为O（1）。

3 买卖股票的最佳时机 II

3.1 题目描述

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

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

3.2 示例

输入: prices = [7,1,5,3,6,4]

输出: 7

输入: prices = [1,2,3,4,5]

输出: 4

3.3 分析与解答

与上一题的区别只有一个，本题可以进行无限次交易而上一题只能进行一次交易。

也就是说，上一题得到的分析结论仍然成立：（1）从始至终只存在三种状态：未进行过股票交易、买入且持有股票、买入且但未持有股票（已经卖出）。（2）第i天处于何种状态及获得怎样的收益只取决于第i - 1天的状态和收益。

不同在于：当第i天处于买入且持有股票状态时这里有三种情况，第一种是第i - 1 天就已经处于该状态，所以利润不变；第二种是第i - 1天处于买入且但未持有股票（已经卖出）的状态，在第i天进行了买入操作，则利润为 sell[i - 1] - prices[i]；第三种是第i - 1天之前都未进行过股票交易，在第i天进行了买入操作，则利润为 0 - prices[i]。但显然，第二种得到的利润一定会比第三种高，所以在计算时可以忽略该状态。

因此状态转移方程（1）发生了改变：$$buy[i]=Math.max(buy[i-1],sell[i-1]-pric$$