0309. 最佳买卖股票时机含冷冻期 · ttttt

# 0309. 最佳买卖股票时机含冷冻期 ## 题目地址(309. 最佳买卖股票时机含冷冻期) <https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/> ## 题目描述 ``` <pre class="calibre18">``` 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] ``` ``` ## 前置知识 - [动态规划](https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md) ## 公司 - 阿里 - 腾讯 - 字节 ## 思路这是一道典型的 DP 问题， DP 问题的核心是找到状态和状态转移方程。这道题目的状态似乎比我们常见的那种 DP 问题要多，这里的状态有 buy sell cooldown 三种，我们可以用三个数组来表示这这三个状态，buy,sell, cooldown. - buy\[i\]表示第 i 天，且以 buy 结尾的最大利润 - sell\[i\]表示第 i 天，且以 sell 结尾的最大利润 - cooldown\[i\]表示第 i 天，且以 sell 结尾的最大利润我们思考一下，其实 cooldown 这个状态数组似乎没有什么用，因此 cooldown 不会对`profit`产生任何影响。我们可以进一步缩小为两种状态。 - buy\[i\] 表示第 i 天，且以 buy 或者 coolwown 结尾的最大利润 - sell\[i\] 表示第 i 天，且以 sell 或者 cooldown 结尾的最大利润对应的状态转移方程如下： > 这个需要花点时间来理解 ``` <pre class="calibre18">``` buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); ``` ``` 我们来分析一下，buy\[i\]对应第 i 的 action 只能是 buy 或者 cooldown。 - 如果是 cooldown，那么 profit 就是 buy\[i - 1\] - 如果是 buy，那么就是`前一个卖的profit减去今天买股票花的钱`，即 sell\[i -2\] - prices\[i\] > 注意这里是 i - 2，不是 i-1 ，因为有 cooldown 的限制 sell\[i\]对应第 i 的 action 只能是 sell 或者 cooldown。 - 如果是 cooldown，那么 profit 就是 sell\[i - 1\] - 如果是 sell，那么就是`前一次买的时候获取的利润加上这次卖的钱`，即 buy\[i - 1\] + prices\[i\] ## 关键点解析 - 多状态动态规划 ## 代码 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=309 lang=javascript * * [309] Best Time to Buy and Sell Stock with Cooldown * */ /** * @param {number[]} prices * @return {number} */ var maxProfit = function (prices) { if (prices == null || prices.length <= 1) return 0; // 定义状态变量 const buy = []; const sell = []; // 寻常 buy[0] = -prices[0]; buy[1] = Math.max(-prices[0], -prices[1]); sell[0] = 0; sell[1] = Math.max(0, prices[1] - prices[0]); for (let i = 2; i < prices.length; i++) { // 状态转移方程 // 第i天只能是买或者cooldown // 如果买利润就是sell[i - 2] - prices[i], 注意这里是i - 2，不是 i-1 ，因为有cooldown的限制 // cooldown就是buy[i -1] buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); // 第i天只能是卖或者cooldown // 如果卖利润就是buy[i -1] + prices[i] // cooldown就是sell[i -1] sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); } return Math.max(buy[prices.length - 1], sell[prices.length - 1], 0); }; ``` ``` ## 相关题目 - [121.best-time-to-buy-and-sell-stock](121.best-time-to-buy-and-sell-stock.html) - [122.best-time-to-buy-and-sell-stock-ii](122.best-time-to-buy-and-sell-stock-ii.html)