本文主要是介绍代码随想路第50天 | 123.买卖股票的最佳时机III 、 188.买卖股票的最佳时机IV，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、前言
参考文献：代码随想录；
今天的主题还是买股票，所以回顾一下昨天的递推公式dp[i][0] = max(dp[i - 1], dp[i - 1][1] + price[i])
大概就是这样，这是可以无限次买卖的版本；
今天的难度又升级了，所以我们继续进步吧！！
二、买卖股票的最佳时机|||
1、思路：
这个要是我一个人想我得想很久，还有可能想不出来。。
首先这个题目的思路和前两个题目的思路大差不差，只是多了几种状态。
我们直接来分析吧！
（1）创建，定义dp数组：
首先我们要知道，这里一共有五种状态：无操作、在第i天第一次持有、在第i天第一次出售、在第i天第二次持有、在第i天第二次出售。所以我们的dp数组是二维的，行记录天数，列记录第i天发生的状态；
vector<vector<int>> dp(price.size(), vector<int> (5, 0));(2）dp的递推公式：
其实发现如果把这五种状态分析出来以后，递推公式就不难得出就是对这五种状况的公式推到：
dp[i][0] = dp[i][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);都是从前面推到后面；
（3）初始化：
有了推导公式我们就可以确定初始化了，就是在第一天的时候将五种状态都初始化出来（一天可以买卖多次）：
// 表示没有操作dp[0][0] = 0;// 表示第一天买入dp[0][1] = -prices[0];// 表示第一天卖出dp[0][2] = 0;// 表示第一天买入第二次dp[0][3] = -prices[0];// 表示第二次卖出dp[0][4] = 0;2、整体代码如下：
class Solution {
public:int maxProfit(vector<int>& prices) {// 1、定义dp数组vector<vector<int>> dp(prices.size(), vector<int> (5));// 2、初始化// 表示没有操作dp[0][0] = 0;// 表示第一天买入dp[0][1] = -prices[0];// 表示第一天卖出dp[0][2] = 0;// 表示第一天买入第二次dp[0][3] = -prices[0];// 表示第二次卖出dp[0][4] = 0;// 3、遍历顺序for (int i = 1; i < prices.size(); i++) {// 递推公式dp[i][0] = dp[i][0];dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);}int result = 0;// 打印dpfor (auto i : dp) {for (auto j : i) {result = result > j ? result : j;}}return result;}
};在最后的返回时可以做一个小小的优化，就是把找最大值改为：dp[price.size() - 1][4]；
因为在最后一次卖出时，所得到一定是最大值！
三、买卖股票的最佳时机IV
1、、思路：
与上一题思路一样，但是买卖次数变成了一个变量；
但是观察发现，之前的初始化和递推公式都有着相似之处，所以可以利用这些相似之处不难写出:
// 2、初始化dp[0][0] = 0;for (int i = 1; i <= 2 * k; i++) {if (i % 2 == 0) {dp[0][i] = 0;} else {dp[0][i] = -prices[0];}}
类似于这样的代码，让初始化和递推公式随k变化；
2、整体代码如下：
class Solution {
public:int maxProfit(int k, vector<int>& prices) {// 1、定义dp数组vector<vector<int>> dp(prices.size(), vector<int> (2 * k + 1, 0));// 2、初始化dp[0][0] = 0;for (int i = 1; i <= 2 * k; i++) {if (i % 2 == 0) {dp[0][i] = 0;} else {dp[0][i] = -prices[0];}}// 3、遍历顺序for (int i = 1; i < prices.size(); i++) {// 4、递推公式dp[i][0] = dp[i - 1][0];for (int j = 1; j <= 2 * k; j++) {if (j % 2 == 0) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);} else {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);}}}// 最后一次卖出的一定是最大值return dp[prices.size() - 1][2 * k];}
};Time to study:1h
leave message:
Respect your efforts, respect yourself. Self-respect leads to eslf-discipline. When you have both firmly under your belt, that's real power.
尊重你的努力，尊重你自己，自尊带来自律。当你把两者都牢牢地绑在自己身上时，就会产生真正的力量。
这篇关于代码随想路第50天 | 123.买卖股票的最佳时机III 、 188.买卖股票的最佳时机IV的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
