Skip to content

Latest commit

 

History

History
106 lines (78 loc) · 3.52 KB

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

File metadata and controls

106 lines (78 loc) · 3.52 KB
Raw

题目地址

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

题目描述

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)
Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

思路

这是一道典型的 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);
};

相关题目