Keshawn_lu's Blog

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

动态规划
字数统计: 883阅读时长: 3 min
2020/07/10 Share

题目简介：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

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

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

示例:

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

思路：

一开始自己想到的动态规划方法参照了昨天做的 恢复空格 的方法，dp[i]代表第i天结束后的最大收益。

首先dp[i] = dp[i - 1]进行初始化，然后j从0遍历到i，使第j天买入，第i天卖出的收益加上dp[j - 2]的值最大(由于第j天买入，且存在冷冻期，所以第j - 1天必不可能卖出股票；采用dp[j - 2]是假设第j - 2天卖出股票，以达到更多次数的买卖股票目的)，从而不断更新dp[i]。

缺点就是时间复杂度为O(n^2)，比较慢。

然后看了大家的题解，发现可以使用二维dp，实现不同的状态。

我们假设dp[i][0,1,2]为第i天结束以后的最大收益。

  • dp[i][0]为该天未持股，且无操作(该天啥也没做)。
  • dp[i][1]为该天结束后变成冷冻期(该天卖出了股票)。
  • dp[i][2]为该天持股，可能是这天买了股票也可能之前一直没卖。

首先进行初始化，dp[0][0] = 0, dp[0][1] = 0，dp[0][2] = -prices[0](该天买了股票)。

dp[i][0]有两种情况来生成：

  1. 前一天本身就没有股票
  2. 前一天卖出了股票，变成了冷冻期。

所以dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])。

dp[i][1]只有一种情况，只有当天卖出股票才会进入冷冻期，所以dp[i][1] = dp[i - 1][2] + prices[i]。

dp[i][2]有两种情况：

  1. 前一天本身就有股票，且没卖，留到了今天。
  2. 之前没有股票，今天买了股票。

所以dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] - 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
class Solution {
public:
    int maxProfit(vector<int>& prices) {

        if(prices.size() < 2)
            return 0;

        vector<int> dp(prices.size(), 0);

        for(int i = 1; i < prices.size(); i++){

            dp[i] = dp[i - 1];  //默认冷冻期

            for(int j = 0; j < i; j++){

                if(j < 2)
                    dp[i] = max(dp[i], prices[i] - prices[j]);
                else
                    dp[i] = max(dp[i], dp[j - 2] + prices[i] - prices[j]);
            }
        }

        return dp[prices.size() - 1];

    }
};

方法二：

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(vector<int>& prices) {

        if(prices.size() < 2)
            return 0;

        vector<vector<int>> dp(prices.size(), vector<int>(3, 0));

        //第i天结束以后的最大收益
        //dp[i][0]  //未持股(该天啥也没做)
        //dp[i][1]  //冷冻期(该天卖出了股票)
        //dp[i][2]  //持股
        dp[0][2] = -prices[0];   //买了一股

        for(int i = 1; i < prices.size(); i++){

            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);

            dp[i][1] = dp[i - 1][2] + prices[i];    //卖出股票才会进入冷冻期

            dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] - prices[i]);
        }

        return max(max(dp[prices.size() - 1][0], dp[prices.size() - 1][1]), dp[prices.size() - 1][2]);

    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网