Skip to content

Latest commit

 

History

History
137 lines (107 loc) · 4.31 KB

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

File metadata and controls

137 lines (107 loc) · 4.31 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
 *
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
 *
 * algorithms
 * Medium (43.52%)
 * Total Accepted:    88.3K
 * Total Submissions: 201.4K
 * Testcase Example:  '[1,2,3,0,2]'
 *
 * Say you have an array for which the i^th 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]
 *
 */
/**
 * @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);
};

相关题目