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

题目链接

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

题目描述

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

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

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

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

示例 2:

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

提示：

• $1\le prices.length\le 5000$
• $0\le prices[i]\le 1000$

解法一：记忆化搜索

• 我们定义 $dfs(i,0)$ 为到第 $i$ 天结束，不持有股票 的最大利润；
• 我们定义 $dfs(i,1)$ 为到第 $i$ 天结束，持有股票 的最大利润；

我们可以根据题目要求，画出如下状态机模型：

我们注意到：如果在第 $i$ 天完成了一笔交易（即卖出了持有的股票），那么最早只能在 第 $i+2$ 天才能重新买入股票。

{ d f s ( i , 1 ) = m a x { d f s ( i − 1 , 1 ) , d f s ( i − 2 , 0 ) − p r i c e s [ i ] } d f s ( i , 0 ) = m a x { d f s ( i − 1 , 0 ) , d f s ( i − 1 , 1 ) + p r i c e s [ i ] } {dfs(i,1)=max{dfs(i−1,1),dfs(i−2,0)−prices[i]}dfs(i,0)=max{dfs(i−1,0),dfs(i−1,1)+prices[i]}

{dfs(i,1)=max{dfs(i−1,1),dfs(i−2,0)−prices[i]}dfs(i,0)=max{dfs(i−1,0),dfs(i−1,1)+prices[i]}​

对于 $i<0$ 的边界条件：

d f s ( i , j ) = { 0 if i < 0 , j = 0 − ∞ if i < 0 , j = 1 dfs(i,j) = {0ifi<0,j=0−∞ifi<0,j=1

dfs(i,j)={0ifi<0,j=0−∞ifi<0,j=1​

时间复杂度： $O(n)$

C++代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int f[n][2];
        memset(f,-1,sizeof f);

        function<int(int,int)> dfs = [&](int i,int hold) -> int{
            if(i < 0){
                return hold ? -1e9 : 0;
            }
            if(f[i][hold] != -1) return f[i][hold];

            //持有股票
            if(hold) f[i][1] = max(dfs(i - 1,1),dfs(i - 2,0) - prices[i]);
            else f[i][0] = max(dfs(i - 1,0) , dfs(i - 1,1) + prices[i]);

            return f[i][hold];
        };

        return dfs(n - 1,0);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

解法二：动态规划

将 记忆化搜索 转为 动态规划（递推）：

{ f [ i ] [ 1 ] = m a x { f [ i − 1 ] [ 1 ] , f [ i − 2 ] [ 0 ] − p r i c e s [ i ] } f [ i ] [ 0 ] = m a x { f [ i − 1 ] [ 0 ] , f [ i − 1 ] [ 1 ] + p r i c e s [ i ] } {f[i][1]=max{f[i−1][1],f[i−2][0]−prices[i]}f[i][0]=max{f[i−1][0],f[i−1][1]+prices[i]}

{f[i][1]=max{f[i−1][1],f[i−2][0]−prices[i]}f[i][0]=max{f[i−1][0],f[i−1][1]+prices[i]}​

我们目前不能处理 $i<0$ 的情况。所以我们可以将其整体向后偏移一位，用 $f[0][j]$ 来表示 $i<0$ 的情况，即：

f [ 0 ] [ j ] = { 0 if j = 0 − ∞ if j = 1 f[0][j] = {0ifj=0−∞ifj=1

f[0][j]={0ifj=0−∞ifj=1​

时间复杂度： $O(n)$

C++代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int f[n+1][2];
        memset(f,0x80,sizeof f);

        f[0][0] = 0;
        f[1][0] = 0 , f[1][1] = -prices[0];
        for(int i = 2;i <= n;i++){
            f[i][1] = max(f[i - 1][1] , f[i - 2][0] - prices[i - 1]);
            f[i][0] = max(f[i - 1][0] , f[i - 1][1] + prices[i - 1]);
        }

        return f[n][0];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17