309. 买卖股票的最佳时机含冷冻期_买卖股票的最佳时机含冷冻期 原题链接

原题链接：

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

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

完成情况：

解题思路：

	//卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
	/*
	很经典的dp题目。= =~

	我们用 f[i]表示第 i 天结束之后的「累计最大收益」。
    根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：
        -我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
        -我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
        -我们目前不持有任何股票，并且【不处于】冷冻期中，对应的「累计最大收益」记为 f[i][2]。

    如何进行状态转移呢？在第 iii 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i天的状态会从第 i−1天的状态转移而来；我们也可以不进行任何操作，此时第 i天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：
    ●对于 f[i][0]，我们目前持有的这一支股票可以是在第 i−1天就已经持有的，对应的状态为 f[i−1][0]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1][2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：
         f[i][0]=max(f[i−1][0],f[i−1][2]−prices[i])
    ●对于 f[i][1]，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 f[i−1][0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：
         f[i][1]=max(f[i−1][0],f[i−1][2]−prices[i])
    ●对于 f[i][2]，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1][1]；如果不处于冷冻期，对应的状态为 f[i−1][2]。因此状态转移方程为：
         f[i][2]=max(f[i−1][1],f[i−1][2])

    这样我们就得到了所有的状态转移方程。如果一共有 n 天，那么最终的答案即为：
        max(f[n−1][0],f[n−1][1],f[n−1][2])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

参考代码：

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

package 西湖算法题解___中等题;

public class __309买卖股票的最佳时机含冷冻期 {
	public int maxProfit(int[] prices) {
		//卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
		/*
		很经典的dp题目。= =~

		我们用 f[i]表示第 i 天结束之后的「累计最大收益」。
        根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：
            -我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
            -我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
            -我们目前不持有任何股票，并且【不处于】冷冻期中，对应的「累计最大收益」记为 f[i][2]。

        如何进行状态转移呢？在第 iii 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i天的状态会从第 i−1天的状态转移而来；我们也可以不进行任何操作，此时第 i天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：
        ●对于 f[i][0]，我们目前持有的这一支股票可以是在第 i−1天就已经持有的，对应的状态为 f[i−1][0]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1][2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：
             f[i][0]=max(f[i−1][0],f[i−1][2]−prices[i])
        ●对于 f[i][1]，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 f[i−1][0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：
             f[i][1]=max(f[i−1][0],f[i−1][2]−prices[i])
        ●对于 f[i][2]，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1][1]；如果不处于冷冻期，对应的状态为 f[i−1][2]。因此状态转移方程为：
             f[i][2]=max(f[i−1][1],f[i−1][2])

        这样我们就得到了所有的状态转移方程。如果一共有 n 天，那么最终的答案即为：
            max(f[n−1][0],f[n−1][1],f[n−1][2])
		 */
		int n =  prices.length;
		if(n == 0){
			return 0;
		}

		int f_dp [][] = new int[n][3];
		f_dp[0][0] = -prices[0];    //我们看的是，收益，第一个你可以选择跳过，也可以选择买入，买入即为负数
		for (int i=1;i<n;i++){
			f_dp[i][0] = Math.max(f_dp[i-1][0],f_dp[i-1][2] - prices[i]);
			f_dp[i][1] = f_dp[i-1][0] + prices[i];
			f_dp[i][2] = Math.max(f_dp[i-1][1],f_dp[i-1][2]);
		}
		return Math.max(f_dp[n-1][1],f_dp[n-1][2]);
	}
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41

__309买卖股票的最佳时机含冷冻期__空间优化

package 西湖算法题解___中等题;

public class __309买卖股票的最佳时机含冷冻期__空间优化 {
	public int maxProfit(int[] prices){
		//卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
		/*
		很经典的dp题目。= =~

		我们用 f[i]表示第 i 天结束之后的「累计最大收益」。
        根据题目描述，由于我们最多只能同时买入（持有）一支股票，并且卖出股票后有冷冻期的限制，因此我们会有三种不同的状态：
            -我们目前持有一支股票，对应的「累计最大收益」记为 f[i][0]；
            -我们目前不持有任何股票，并且处于冷冻期中，对应的「累计最大收益」记为 f[i][1]；
            -我们目前不持有任何股票，并且【不处于】冷冻期中，对应的「累计最大收益」记为 f[i][2]。

        如何进行状态转移呢？在第 iii 天时，我们可以在不违反规则的前提下进行「买入」或者「卖出」操作，此时第 i天的状态会从第 i−1天的状态转移而来；我们也可以不进行任何操作，此时第 i天的状态就等同于第 i−1 天的状态。那么我们分别对这三种状态进行分析：
        ●对于 f[i][0]，我们目前持有的这一支股票可以是在第 i−1天就已经持有的，对应的状态为 f[i−1][0]；或者是第 i 天买入的，那么第 i−1 天就不能持有股票并且不处于冷冻期中，对应的状态为 f[i−1][2] 加上买入股票的负收益 prices[i]。因此状态转移方程为：
             f[i][0]=max(f[i−1][0],f[i−1][2]−prices[i])
        ●对于 f[i][1]，我们在第 i 天结束之后处于冷冻期的原因是在当天卖出了股票，那么说明在第 i−1 天时我们必须持有一支股票，对应的状态为 f[i−1][0] 加上卖出股票的正收益 prices[i]。因此状态转移方程为：
             f[i][1]=max(f[i−1][0],f[i−1][2]−prices[i])
        ●对于 f[i][2]，我们在第 i 天结束之后不持有任何股票并且不处于冷冻期，说明当天没有进行任何操作，即第 i−1 天时不持有任何股票：如果处于冷冻期，对应的状态为 f[i−1][1]；如果不处于冷冻期，对应的状态为 f[i−1][2]。因此状态转移方程为：
             f[i][2]=max(f[i−1][1],f[i−1][2])

        这样我们就得到了所有的状态转移方程。如果一共有 n 天，那么最终的答案即为：
            max(f[n−1][0],f[n−1][1],f[n−1][2])
		 */
		int n = prices.length;
		if (prices.length == 0){
			return 0;
		}
		int f0_dp = -prices[0];
		int f1_dp = 0;
		int f2_dp = 0;
		for (int i=1;i<n;i++){
			int new_f0_dp = Math.max(f0_dp,f2_dp - prices[i]);
			int new_f1_dp = f0_dp + prices[i];
			int new_f2_dp = Math.max(f1_dp,f2_dp);
			f0_dp = new_f0_dp;
			f1_dp = new_f1_dp;
			f2_dp = new_f2_dp;
		}
		return Math.max(f1_dp,f2_dp);
	}
}

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44