🍇188. 买卖股票的最佳时机 IV
🍋题目描述
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3] 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
🍑思路分析
这道题算是上个题的进阶版,要求至多k次交易
动规五部曲
确定dp数组以及下标的含义
二维数组dp[i] [j] :第i天的状态为j,所剩下的最大现金是dp[i] [j]
j的状态表示为:
0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
…
可以发现规律: 除了0以外,偶数就是卖出,奇数就是买入.
题目要求最多K笔交易,那么j 的范围就是 0 - 2 * k (也就是2*k+1种状态)
确定递推公式
达到dp[i] [1]状态，有两个具体操作：
操作一：第i天买入股票了，那么dp[i] [1] = dp[i - 1] [0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]
选最大的，所以 dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
同理dp[i] [2]也有两个操作：
操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]
所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
同理可以类比剩下的状态，代码如下：
for(int j = 1;j <= 2*k; j+=2) { dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//第j/2次买入的利润 dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]+prices[i]);//第j/2次卖出的利润 }
dp数组如何初始化
第0天没有操作,就是0, 即dp[0] [0] = 0
第0天做第一次买入操作,dp[0] [1] = -prices[0]
第0天做第一次卖出的操作,因为第0天嘛,都没股票(无法卖出),所以就是0了,即dp[0] [2] = 0
第0天第二次买入操作.第二次买入依赖于第一次卖出的状态,就相当于第0天第一次买入了,然后又卖出了(一进一出获利为0).然后开始第二次买入. 即dp[0] [3] = -prices[0]
第0天第二次卖出操作. dp[0] [4] = 0;
…
可以观察到,对于dp[0] [j],当j为奇数的时候都初始化为-prices[0],为偶数的时候都初始化为0
确定遍历顺序
从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
举例推导dp数组
以输入[1,2,3,4,5]，k=2为例。
最后一次卖出，一定是利润最大的，**dp[prices.size() - 1] [2 * k]**即红色部分就是最后求解。
🍠参考代码
#include<bits/stdc++.h> using namespace std; int maxProfit(int k, vector<int>& prices) { if(prices.size()==0 || prices.size()==1) { return 0; } vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));//dp定义 //dp初始化 dp[0][0] = 0,第一次买入、卖出 dp[0][1] = -prices[0] dp[0][2] = 0；第二次买入、卖出dp[0][3] = -prices[0] dp[0][4] = 0... for(int i = 1;i <= 2*k;i+=2){//奇数初始化为 -1*prices[0] dp[0][i] = -1*prices[0]; } //进行递推 for(int i = 1; i < prices.size(); i++) { //持有dp[i][0]不用管,永远和上一个dp[i-1][0]相等. for(int j = 1;j <= 2*k; j+=2) { dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]-prices[i]);//第j/2次买入的利润 dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j]+prices[i]);//第j/2次卖出的利润 } } return dp[prices.size()-1][2*k]; }
🍓714. 买卖股票的最佳时机含手续费
🍆题目描述
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2 输出：8 解释：能够达到的最大利润: 在此处买入 prices[0] = 1 在此处卖出 prices[3] = 8 在此处买入 prices[4] = 4 在此处卖出 prices[5] = 9 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3 输出：6
🍌思路分析
相对于**[动态规划：122.买卖股票的最佳时机II]**，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。
唯一差别在于递推公式部分，所以接下来分析一下递推公式部分。
这里重申一下dp数组的含义：
dp[i] [0] 表示第i天持有股票所省最多现金。 dp[i] [1] 表示第i天不持有股票所得最多现金
🍍🍍🍍如果第i天持有股票即dp[i] [0]， 那么可以由两个状态推出来
第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1] [0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
🍠🍠🍠如果第i天不持有股票即dp[i] [1]的情况， 依然可以由两个状态推出来
第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1] [1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee
所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
🍇参考代码
#include<bits/stdc++.h> using namespace std; int maxProfit(vector<int>& prices, int fee) { vector<vector<int>> dp(prices.size(),vector<int>(2,0));//定义dp //初始化 dp[0][0] -= prices[0];//持有 dp[0][1] = 0;//不持有 for(int i = 1; i < prices.size(); i++) { dp[i][0] = max(dp[i-1][0],dp[i-1][1] - prices[i]);//持有时的获利: = max(之前持有的利润 ,之前未持有但是现在买入持有的利润) dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);//不持有时的获利: = max(之前不持有利润,之前持有本次卖出的利润) } return dp[prices.size()-1][1]; }
以上相关题解来源于卡尔大佬的代码随想录
如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客
