代码随想录算法训练营Day51|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结

本文主要是介绍代码随想录算法训练营Day51|309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

前言

思路

算法实现

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

前言

思路

算法实现

股票问题总结

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

题目链接

文章链接

前言

本题在买卖股票II的基础上增加了一个冷冻期，因此就不能简单分为持有股票和卖出股票两个状态了。

思路

利用动规五部曲进行分析：

1.确定dp数组及其下标的含义：

dp[i][j]：第i天状态为j，所剩的最多现金为dp[i][j]；

本题的状态j可以分为如下四个状态：

状态一：持有股票状态；
因为冷冻期的存在，由不持有股票状态，引申出以下两种状态：

状态二：保持卖出股票的状态（两天前就卖出了股票，并且已经度过了冷冻期，并保持未购入股票的状态）；

状态三：今天卖出股票；

状态四：冷冻期；

2.确定递推公式：

对于状态一的前一天可能有多种情况：

情况一：前一天也为持有股票状态，dp[i][0] = dp[i - 1][0];

情况二：前一天为处于保持卖出股票的状态，第i天购入股票，则dp[i][0] = dp[i - 1][1] - prices[i];

情况三：前一天刚好为冷冻期，第i天购入股票，则dp[i][0] = dp[i - 1][3] - prices[i]；

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

对于状态二的前一天也不止一种情况：

情况一：前一天额为保持卖出的状态，dp[i][1] = dp[i - 1][1];

情况二：前一天为冷冻期，第i天恰好未保持卖出的状态，dp[i][1] = dp[i - 1][3] - prices[i];

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

对于状态三，第i天卖出股票，前一天必为持有股票的状态，即dp[i][2] = dp[i - 1][0] + prices[i];

对于状态四，冷冻期的前一天必定刚好卖出股票，即dp[i][3] = dp[i - 1][2];

3.初始化dp数组：

第0天持有股票，dp[0][0] 一定为-prices[0]，卖出股票后，不管是当天还是冷冻期以及保持卖出股票的状态，所剩余的金钱一定都为0。

因此dp[0][0] = -prices[0], dp[0][1] = 0, dp[0][2] = 0, dp[0][3] = 0;

4.确定遍历顺序：

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

5.打印dp数组：

以 [1,2,3,0,2] 为例，dp数组如下：

算法实现

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

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

题目链接

文章链接

前言

本题依然是买卖股票II的变形，在原题的基础上增加手续费即可。

思路

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

算法实现

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