309 买卖股票的最佳时机含冷冻期（状态机DP）（灵神笔记）

最佳时机含冷冻期（状态机DP）（灵神笔记）"/>

309 买卖股票的最佳时机含冷冻期（状态机DP）（灵神笔记）

题目

链接
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

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

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

示例 1:

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

输入: prices = [1]
输出: 0

提示：

1 <= prices.length <= 5000
0 <= prices[i] <= 1000

题解

记忆化搜索（超时）

class Solution {private int[] prices;private int[][] cache;public int maxProfit(int[] prices) {this.prices = prices;int n = prices.length;cache = new int[n][2];for (int i = 0; i < n; i++) {Arrays.fill(cache[i],-1);}return dfs(n - 1, 0);}private int dfs(int i, int hold) {if (i < 0) {return hold == 1 ? Integer.MIN_VALUE : 0;}if (cache[i][hold] != -1) {return cache[i][hold];}if (hold == 1) {//第i-2天卖出股票return Math.max(dfs(i - 1, 1), dfs(i - 2, 0) - prices[i]);}return Math.max(dfs(i - 1, 0), dfs(i - 1, 1) + prices[i]);}
}

递推

class Solution {public int maxProfit(int[] prices) {int n = prices.length;int[][] f = new int[n + 2][2];f[1][1] = Integer.MIN_VALUE;for (int i = 0; i < n; i++) {f[i + 2][0] = Math.max(f[i + 1][0], f[i + 1][1] + prices[i]);f[i + 2][1] = Math.max(f[i + 1][1], f[i][0] - prices[i]);}return f[n + 1][0];}
}

空间优化

class Solution {public int maxProfit(int[] prices) {int f0 = 0, f1 = Integer.MIN_VALUE, pre0 = 0;for (int p : prices) {int newf0 = Math.max(f0, f1 + p);f1 = Math.max(f1, pre0 - p);pre0 = f0;f0 = newf0;}return f0;}
}