题目描述

题目1: 买卖股票的最佳时机 I。给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

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

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

题目4: 买卖股票的最佳时机 IV。给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

题目5: 买卖股票的最佳时机含手续费。给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易,但是你每次交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

基础解析

通过对
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-w-5/
的阅读,自己理解了,写下自己的理解。

其实这6道题(因为含有冷冻期的那道题昨天已经整理了,故今天没有整理,所以本文中只有5个题)看似不同,但其实都是反映了同一种思路。以第四题为基本,因为第四题其实是一种泛化形式的题目。

第一题只是第四题中当k=1的特例;第二题实际相当于当k=infinity时候的特例;第三题相当于当k=2的时候的特例;第五题和第六题相当于第二题的特例。

我们发现在这个题里面存在三个主动变量(也就是原解析中提到的状态一词),即:第i天价格第k次交易持有或卖出(1或0),所以实际上这个dp数组可以写为dp[i][k][0]dp[i][k][1]。我们想要的答案肯定是dp[i][k][0],因为当第三个状态为1的时候,说明我们还有股票,只有卖出才能有收益。

下面画出状态转移图

通过这个图,我们可以很容易的写出状态转移方程的形式:

dp[i][k][0]=max(dp[i-1][k][0],dp[i-1][k][1]+prices[i])

这个式子的含义是,如果今天我没有持有股票,那么只有两种可能:

  • 昨天的时候我就没有股票,那么铁定至迟在昨天的时候就已经完成了k次交易,所以是dp[i-1][k][0]
  • 昨天我持有股票,今天我把它卖了,由于买一次和卖一次算一次交易,所以昨天也是第k次交易,所以是dp[i-1][k][1]+prices[i]

dp[i][k][1]=max(dp[i-1][k][1]mdp[i-1][k-1][0]-prices[i])

这个式子的含义是,今天我持有股票,那么又是有两种可能:

  • 昨天我持有股票,今天我不卖;
  • 昨天我没有持有,今天我买了,所以今天我进行了第k次交易,故昨天是第k-1的状态。

至此,解决这6个问题的核心已经解决了。接下来就是一些边界问题。

dp[-1][k][0] = 0
解释:因为 i 是从 0 开始的,所以 i = -1 意味着还没有开始,这时候的利润当然是 0 。

dp[-1][k][1] = -infinity
解释:还没开始的时候,是不可能持有股票的,用负无穷表示这种不可能。

dp[i][0][0] = 0
解释:因为 k 是从 1 开始的,所以 k = 0 意味着根本不允许交易,这时候利润当然是 0 。

dp[i][0][1] = -infinity
解释:不允许交易的情况下,是不可能持有股票的,用负无穷表示这种不可能。

第一题解析及代码实现

对于第一题来说,实际上就是k=1的情况,那我们可以将dp数组简化为二维数组,即省略k这一项。写为

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], -prices[i])

为什么第二个式子max的第二项是-prices[i]呢,因为:
dp[i][1]=max(dp[-1][1],dp[-1][0]-prices[i])=max(-infinity, 0-prices[i])=-prices[i]

考虑到一个新的状态只与相邻一个状态有关系,我们可以继续节省空间复杂度,将数组用变量来表示,即dp_i_0相当于原来的dp[i][0],dp_i_1相当于原来的dp[i][1]

代码实现如下:

 int maxProfit(vector<int>& prices) { int len = prices.size(); if (len <= 1) return 0; int dp_i_0 = 0, dp_i_1 = INT_MIN; for (int i = 0; i < len; i++) { dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = max(dp_i_1, -prices[i]); } return dp_i_0;}

第二题解析及代码实现

当k为无穷的时候,实际上k和k-1已经可以看做是一样的,然后继续省略k这一项。这个时候写出来的状态转移方程是

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] – prices[i])

与第一题同理,修改为变量进行更新。但是注意,由于此时k并不是1了,而是可以任意数字了,所以dp[i-1][k-1][0]还是要专门写出来,由于在第一个式子中dp_i_0已经更新为当前这一步的结果,所以在dp_i_0更新之前需要将它的值缓存在t中以便dp_i_1更新时使用。

int maxProfit(vector<int>& prices) { int len = prices.size(); if (len <= 1) return 0; int dp_i_0 = 0, dp_i_1 = INT_MIN; for (int i = 0; i < len; i++) { int t = dp_i_0; dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = max(dp_i_1, t - prices[i]); } return dp_i_0;}

第三题解析及代码实现

k之前都被化简掉了,但是这里k不能做被忽略,所以必须要对k进行穷举。但是由于k在本题只有1和2两种状态,所以实际也可以将其写为变量的形式,即

dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + price);
dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 – price);
dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + price);
dp_i_1_1 = max(dp_i_1_1, -price);

int maxProfit(vector<int>& prices) { int len = prices.size(); if (len <= 1) return 0; int dp_i_1_0 = 0, dp_i_1_1 = INT_MIN; int dp_i_2_0 = 0, dp_i_2_1 = INT_MIN; for (int price : prices) { dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + price); dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - price); dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + price); dp_i_1_1 = max(dp_i_1_1, -price); } return dp_i_2_0;}

第四题解析及代码实现

当k等于任意可能数字的时候,k就有可能大于所给天数的长度,此时就要进行特殊处理。也就是说,此时直接将所有坡度加起来就好了。

而当k小于的时候,就可以正常更新了。因为i只依赖于i-1的情况,所以我们可以省略i这个状态,用二维数组进行更新即可。

int maxProfit(int k, vector<int>& prices) { int len = prices.size(); if (len <= 1||k<1) return 0; //处理k>len/2的情况 if (k >= len / 2) { int res = 0; for (int i = 1; i < len; i++) { if (prices[i] > prices[i - 1]) res += (prices[i] - prices[i - 1]); } return res;//只要后一天比前一天高就卖 } //省略i的表达式,节省空间 vector<vector<int>> dp(k + 1, vector<int>{ 0,INT_MIN }); for (int price:prices) { for (int j = k; j > 0; j--) { dp[j][0] = max(dp[j][0], dp[j][1] + price); dp[j][1] = max(dp[j][1], dp[j - 1][0] - price); } } return dp[k][0];}

第五题解析及代码实现

一次交易一个手续费,所以只需要把手续费从利润中减去即可。也就是

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)

当然fee费用也可以写到第一个数字里,但是此时对于dp[i][1]的初始化应为INT_MIN+fee,不然可能会超出范围导致出错。

 int maxProfit(vector<int>& prices, int fee) { int len = prices.size(); if (len <= 1) return 0; int dp_i_0 = 0, dp_i_1 = INT_MIN; for (int i = 0; i < len; i++) { int dp_temp = dp_i_0; dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = max(dp_i_1, dp_temp-prices[i] - fee); } return dp_i_0;}

有冷冻期的题目的解析

由于有一天冷冻期,所以唯一不同点在于所依赖的不是前一天而是前两天,即将i-1改为i-2。即

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])