309.买卖股票的最佳时机含冷冻期

链接：309.买卖股票的最佳时机含冷冻期
难度：Medium
标签：数组、动态规划
简介：给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格，设计一个算法计算出最大利润。

题解 1 - python

• 编辑时间：2023-10-05
• 执行用时：3408ms
• 内存消耗：560.76MB
• 编程语言：python
• 解法介绍：记忆化递归。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(idx: int, cooldown: bool, cur: int):
            if idx == n: return 0
            res = dfs(idx + 1, False, cur)
            if not cooldown:
                if cur != -inf: res = max(res, dfs(idx + 1, True, -inf) + prices[idx] - cur)
                else: res = max(res, dfs(idx + 1, False, prices[idx]))
            return res
        return dfs(0, False, -inf)
        

题解 2 - typescript

• 编辑时间：2020-07-11
• 执行用时：84ms
• 内存消耗：36.5MB
• 编程语言：typescript
• 解法介绍：我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]f[i][0]；我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]f[i][1]；我们目前不持有任何股票，并且不处于冷冻期中，对应的「累计最大收益」记为 f[i][2]f[i][2]。

function maxProfit(prices: number[]): number {
  const len = prices.length;
  if (len === 0) return 0;
  const dp = new Array(len).fill(0).map(_ => new Array(3).fill(0));
  dp[0][0] = -prices[0];
  for (let i = 1; i < len; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - prices[i]);
    dp[i][1] = dp[i - 1][0] + prices[i];
    dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]);
  }
  return Math.max(dp[len - 1][1], dp[len - 1][2]);
}