121买卖股票的最佳时机I II III IV and 309最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

买卖股票的最佳时机I II III IV and 309最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费"/>

121买卖股票的最佳时机I II III IV and 309最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费

121买卖股票的最佳时机

题目：

给一个数组prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格，你需要选择两个元素，第一个元素的i需要小于第二个元素的i，然后求第二次减去第一次的差，最大值是多少。

思路：

思路就是算出第 i 天不持有股票的最多的现金，这个时候前面可能买了股票卖出了，也可能就一直没买股票，用0 1表示持有股票的状态，1表示不持有，用持有不持有股票衍生出推导公式，算最后第 i 天不持有股票的最多的现金就行

dp[i][0]含义和递推公式：

dp[i][0] 表示第i天持有股票所得最多的现金 ，dp[i][1]表示第i天不持有股票所得最多的现金，

dp[i][0]可以由，第 i-1 天就持有股票的现金和第 i 天才持有股票的现金推出来，求这两选择的最大值，就是dp[i][0]的递推公式。

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

dp[i][0]可以由，第 i-1 天就不持有股票的现金和第 i 天不持有股票的现金推出来（就是第 i 天 的卖出），求这两选择的最大值，就是dp[i][0]的递推公式。

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

初始化：

从推导公式可以看出，dp[0][0]和dp[0][1]是推导的核心，dp[0][0]相当入第0天持有股票，现金是-prices[0]

dp[0][0] -= prices[0];

dp[0][1]相当于第0天不持有股票也就是没买。现金是0。

dp[0][1] = 0;

总代码：

// 版本一
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

122.买卖股票的最佳时机II

题目：

给一个正整数数组，可以按照左到右的顺序，任意选两个值，然后求大的减小的的差值，这个过程可重复无限次，但是只能计算完一次差值后才能进行下一次差值的计算，求每次得出的差值最大之和。

dp数组含义：

• dp[i][0] 表示第i天持有股票所得现金。
• dp[i][1] 表示第i天不持有股票所得最多现金

递推公式：

dp[i][0]可以由，

上一天持有股票的现金 dp[i - 1][0]

上一天持有股票的现金dp[i - 1][1]减去买上一天的股票的现金 prices[i]

（这里和股票I的区别就是可以多次买卖导致，可能存留先前赚取的利润 ）

 推出

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

 dp[i][1]可以由，

上一天不持有股票的现金 dp[i - 1][1]

上一天不持有股票的现金 dp[i - 1][1] 加上 上一天卖出股票的现金 prices[i]

推出

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]);

 总代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};

123.买卖股票的最佳时机III

 题目：

给一个数组，数组里的第i个元素表示第i天，值表示当天股票价格，最多交易两次，求最大利润和（一次交易完成才能进行下一个交易）

思路：

有递推关系的感觉，动态规划，设置求题目所求的dp数组含义，有不同状态可以让数组多一个维度表示这个状态，思考不同状态的dp数组的递推关系，怎么由上一个推来，根据题目含义或公式要求求初始化，确定递推顺序。

dp数组含义：

一天一共五个状态，

0.没有操作 

1.第一次持有股票

2.第一次不持有股票

3.第二次持有股票

4.第二次不持有股票

在dp[i][j]中用 j 表示 范围0-4，含义是0-4状态下，第 i 天 的最大现金数。

递推公式：

dp[i][0]只能由一个状态推出来 dp[i][0] = dp[i-1][0]

达到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])

同理可推出剩下状态部分：

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]);

初始化：

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，这个初始值应该是多少呢？

此时还没有买入，怎么就卖出呢？ 其实大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，初始值应该是多少呢？应该不少同学疑惑，第一次还没买入呢，怎么初始化第二次买入呢？

第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。

所以第二次买入操作，初始化为：dp[0][3] = -prices[0];

同理第二次卖出初始化dp[0][4] = 0;

总代码：

（copy了，一看就理解了，不自己写了）

class Solution {
public:int maxProfit(vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(5, 0));dp[0][1] = -prices[0];//这里没写0 2 5 的初始化0，因为上面数组初始化为0了dp[0][3] = -prices[0];for (int i = 1; i < prices.size(); i++) {dp[i][0] = dp[i - 1][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]);}return dp[prices.size() - 1][4];}

188.买卖股票的最佳时机IV 

题目：

同股票III，但是最多k次交易

思路：

0.没有操作 

1.第一次买入股票

2.第一次卖出股票

3.第二次买入股票

4.第二次卖出股票

........第k次买入股票，第k次卖出

通过这个可以看出，除了0之外，奇数买入，偶数卖出，此外最多k次交易的状态数量是2k+1

（我的理解：一次交易有两个状态加一个 0 的状态。）

dp数组含义：

在dp[i][j]中用 j 表示 范围 0-2k+1，含义是 0-2k+1 状态下，第 i 天 的最大现金数。

递推公式：

dp[i][0]就延续自身状态

达到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 = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

 初始化：

同样类推,

第0天没有操作,即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，当天买入，当天卖出，dp[0][2] = 0;

第0天做第二次买入操作，当天买入，当天卖出，同时当天第二次买入，dp[0][3] = -prices[0];

第0天做第二次卖出操作，当天买入，当天卖出，同时当天第二次买入卖出，dp[0][4] = 0;

所以同理可以推出dp[0][j]当j为奇数的时候都初始化为 -prices[0]

提取规律：

for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];
}

 总代码：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

309.最佳买卖股票时机含冷冻期

题目：

同股票II，但每一次交易后会有一天不能交易的冷冻期。（买入没有卖出有）

思路：

加上1天冷冻期后，状态的变化，然后推导对应的递推公式和初始化

• 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
• 不持有股票状态，这里就有两种卖出股票状态
  • 状态二：之前卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
  • 状态三：今天卖出股票
• 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！

增加的状态维度 j 的状态含义为：

• 0：状态一
• 1：状态二
• 2：状态三
• 3：状态四

递推公式的变化

四个状态的推导

达到持有股票状态（状态一）即：dp[i][0]，有两个具体操作：

• 途径一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
• 途径二：今天买入了股票达到了持有状态，有两种情况
  • 前一天是冷冻期（状态四），然后今天买入 - prices[i]，dp[i - 1][3] - prices[i]
  • 前一天是之前卖出股票的状态（状态二），然后今天买入 - prices[i]，dp[i - 1][1] - prices[i]

那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到之前卖出股票的状态（状态二）即：dp[i][1]，有两个具体操作：

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

昨天卖出了股票（状态三）dp[i][3] = dp[i - 1][2];

• 途径一：前一天就是状态二，dp[i - 1][1]
• 途径二：前一天是冷冻期（状态四），dp[i - 1][3]

综上分析，递推代码如下：

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

为啥要把不持有股票状态拆成之前不持有和今天不持有两个状态呢？

因为本题我们有冷冻期，而冷冻期的前一天，只能是 「今天卖出股票」状态，如果是 「之前不持有股票状态」那么就很模糊，因为不一定是 卖出股票的操作。

总代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));}
};

714.买卖股票的最佳时机含手续费

题目：同股票II，但每次交易会扣一次手续费。

卖出操作上，减去一次手续费就是不同：  dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

总代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {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);}return dp[len - 1][1];}
};

总结

代码随想录

冷冻期....真冷