Skip to content

Latest commit

 

History

History
117 lines (84 loc) · 3.67 KB

309.best-time-to-buy-and-sell-stock-with-cooldown.md

File metadata and controls

117 lines (84 loc) · 3.67 KB
Raw

题目地址(309. 最佳买卖股票时机含冷冻期)

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

前置知识

公司

  • 阿里
  • 腾讯
  • 字节

思路

这是一道典型的 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 结尾的最大利润

对应的状态转移方程如下：

这个需要花点时间来理解

  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]

关键点解析

  • 多状态动态规划

代码

/*
 * @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);
};

相关题目