题目描述
题目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])
文章评论