最佳买卖股票时机含冷冻期
力扣题目链接(opens new window)
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 思路本题在 买卖II 的基础上多了一个条件：即卖出股票后的一天不能交易（冷冻期）
我们在分析买卖II时有： 持有 和 不持有 两种状态，并且这两种状态中又细分为 当天 买入/卖出 和 前一天 买入/卖出
因为本题加了冷冻期，所以状态会有不同，大体上可以分为： 持有股票 、 不持有股票 和 处于冷冻期 三大类
五步走 1、确定dp数组含义持有股票 可以视为 状态1 （今天买入或者前一天买入，因为引入了冷冻期，其中还有细分情况后面说）
基于此，我觉得买卖II的状态也是可以缩减的（但这么做可能就不够直观了）
因为有冷冻期限制卖出的操作，所以不持有股票时还是要细分为 两种情况 ：
保持之前不持有股票的状态 视为 状态2
今天卖出股票 视为 状态3
最后，也是新增的一个状态，即 卖出股票后的冷冻期 ，视为 状态4
综上，本题一共有以下四种状态：
状态1---持有股票（j = 0） 不持有股票 状态2---保持不持有状态（j = 1） 状态3---今天卖掉股票（j = 2） 状态4---冷冻期（j = 3）
和 买卖II 一样，我们仍需要使用二维dp数组 dp[i][j] 来表示状态：代表 第i天某种状态下得到的最大收益
2、确定递推公式 （1）持有（买入）股票 dp[i][0] （状态1）要达到 dp[i][0] ，可以有两个途径： 今天买入股票 、 前一天买入股票
今天买入股票又分为三种情况
（买入）前一天是冷冻期（状态4，j = 3），即冷冻期一结束马上买入， dp[i][0] = dp[i - 1][3] - prices[i] （买入）前一天是不持有股票状态（状态2，j = 1），即 昨天之前就已经卖掉股票并过了冷冻期，但是还没有买入股票，今天买入 ， dp[i][0] = dp[i - 1][1] - prices[i]两者取最大值 max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);
（维持状态即前一天买入股票）前一天是保持着上一天买入的状态（状态1，j = 0），并持续到今天， dp[i][0] = dp[i - 1][0]综上， 持有股票状态(状态1) 的递推公式是: dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
（2）不持有股票，保持不持有状态 dp[i][1] （状态2） 前一天为冷冻期（状态4，j = 3），即 两天之前卖掉了股票，经过一天冷冻期到今天 就是不持有状态（不用再加prices）， dp[i][1] = dp[i - 1][3] 前一天就是不持有股票的状态（状态2，j = 1），即在 昨天之前就已经卖掉股票并度过了冷冻期 ， dp[i][1] = dp[i - 1][1]综上， 保持不持有状态（状态2） 的递推公式是： dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
（3）今天卖掉股票 dp[i][2] （状态3） 前一天为冷冻期（状态4，j = 3），即 冷冻期刚结束马上又卖出 ， dp[i][2] = dp[i - 1][3] + prices[i] 前一天为持有股票状态（状态1，j = 0）， dp[i][2] = dp[i - 1][0] + prices[i]综上， 今天卖掉股票（状态3） 的递推公式是： dp[i][2] = max(dp[i - 1][3] + prices[i], dp[i - 1][0] + prices[i]);
综上， 今天卖掉股票（状态3） 的递推公式是： dp[i][2] = dp[i - 1][0] + prices[i];
处于冷冻期就表明之前的一天一定卖出了股票，因此卖掉股票（即状态3）的前置状态不可能是冷冻期（状态4），刚卖完股票还没买呢没东西可卖
（4）冷冻期 dp[i][3]冷冻期的前置状态只可能是前一天卖出股票 （状态3）， dp[i][3] = dp[i - 1][2]
总结一下上面三大类，四种状态
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] = max(dp[i - 1][3] + prices[i], dp[i - 1][0] + prices[i]); dp[i][2] = dp[i - 1][0] + prices[i]; dp[i][3] = dp[i - 1][2]；
这就是全部状态的递推公式
3、初始化dp数组有以下几种情况需要进行初始化
（1） 第0天买入股票（状态1） （一定是买入而不是持有，因为第0天不会有前一天的状态延续）
这种情况下肯定初始金钱为0，那么 dp[0][0] = -prices[0]
（2） 第0天保持不持有状态（状态2）
要找的是 dp[0][1] 的情况，要在i等于1时讨论，即 dp[1][1] = max(dp[0][1], dp[0][3]);
此时 dp[0][1] 要取0
dp[1][1] 指的是第1天保持不持有状态，要在上述二者中取一个最大值
理解1：
那肯定是要使 dp[0][3] 更大一些才对啊，因为这是冷冻期状态，意味着已经卖过一次股票，手里肯定有钱
故为了不影响 dp[0][3] ， dp[0][1] 要取0
理解2：
第0天保持不持有状态 和 第0天冷冻期状态 都是 第1天保持不持有状态 的前置状态，既然最终目的都是要让第1天保持不持有状态，那么其实 dp[0][3] 和 dp[0][1] 都可以取0，这也解释了 dp[0][3] 应该初始化为0的原因
（3） 第0天卖出股票（状态3）
要找的是 dp[0][2] 的情况，也要在i等于1时讨论，结果与上面讨论状态2第0天初始化是同理的， dp[0][2] 也应该取0
此外， dp[0][3] 也初始化为0，见理解2↑
4、确定遍历顺序从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。
代码 class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() == 0) return 0;
//定义dp数组
vector<vector<int>> dp(prices.size(), vector<int>(4, 0));
//初始化
dp[0][0] = -prices[0];
//遍历dp数组
for(int i = 1; i < prices.size(); ++i){
//买入股票:
//维持前一天买入股票的状态
//前一天是冷冻期（状态4，j = 3），冷冻期一结束马上买入
//前一天是不持有股票状态（状态2，j = 1），昨天之前就已经卖掉股票并过了冷冻期，但是还没有买入股票，今天买入
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
//不持有股票
//前一天为冷冻期（状态4，j = 3），两天之前卖掉了股票，经过一天冷冻期到今天
//前一天就是不持有股票的状态,昨天之前就已经卖掉股票并度过了冷冻期
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];//前一天为持有股票状态（状态1，j = 0）
dp[i][3] = dp[i - 1][2];//前一天卖出股票（状态3）
}
//状态2、3、4都有可能是最大值
return max(dp[prices.size() - 1][3], max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]));
}
};
状态2---保持不持有状态（已经卖掉股票）
状态3---今天卖掉股票
状态4---冷冻期（卖掉股票才可能进入冷冻期）
为什么返回的是状态状态2、3、4中的最大值，因为这三个状态都卖出了股票， 最后卖出股票才有可能得到最大收益
至于为什么状态2、3单独取max？其实无所谓顺序，只是max一次只能输入两个比较值所以要这样写
买卖股票的最佳时机含手续费
力扣题目链接(opens new window)
给定一个整数数组 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.注意:
0 < prices.length <= 50000. 0 < prices[i] < 50000. 0 <= fee < 50000 思路与买卖II几乎一样，只是需要加入手续费的处理逻辑即可
再推导一下所有的情况吧
（1）持有股票 dp[i][0]
如果是第i天买入的，那么要用没有持有该股票时有的钱减去股票的售价，即 dp[i][0] = dp[i - 1][1] - prices[i]
如果是第i-1天买入的，就还是和上一题一样，状态延续到第i天即可，即 dp[i][0] = dp[i - 1][0]
综上， dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);//持有
（2）不持有股票 dp[i][1]
如果是第i天卖掉的，那就要用持有该股票时有的钱加上卖股票得的钱 然后还要减掉手续费 ，即 dp[i][1] = dp[i - 1][0] + prices[i] - fee
如果是第i-1天卖掉的，延续第i天的状态即可，即 dp[i][1] = dp[i - 1][1]
综上， 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) {
int n = prices.size();//获取prices数组长度（天数）
vector<vector<int>> dp(n, vector<int>(2, 0));//创建dp数组
dp[0][0] -= prices[0]; //初始化
//dp[0][1] = 0;
for (int i = 1; i < n; 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[n - 1][0], dp[n - 1][1]);//最后一天要求把股票卖掉，返回不持有股票的最大金钱数
}
};
查看更多关于【LeetCode动态规划#13】买卖股票含冷冻期（状态众多，比较繁琐）、含手续费的详细内容...