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]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

递推

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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

空间优化

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12