当前位置：首页 > article >正文

Day44 | 动态规划：状态机DP 买卖股票的最佳时机IV买卖股票的最佳时机III

article 2024/11/15 6:56:00

Day44 | 动态规划：状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期

动态规划应该如何学习？-CSDN博客

本次题解参考自灵神的做法，大家也多多支持灵神的题解

买卖股票的最佳时机【基础算法精讲 21】_哔哩哔哩_bilibili

希望读者在阅读之前先看完这篇博客

Day43 | 动态规划：状态机DP 买卖股票的最佳时机&&买卖股票的最佳时机II-CSDN博客

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

文章目录

Day44 | 动态规划：状态机DP 买卖股票的最佳时机IV&&买卖股票的最佳时机III&&309.买卖股票的最佳时机含冷冻期
- 188.买卖股票的最佳时机IV
- - 思路分析（子问题）：
  - 1.回溯 DFS
  - 2.记忆化搜索
  - 3.1:1翻译为动态规划
  - 4.滚动数组优化
- 123.买卖股票的最佳时机III

188.买卖股票的最佳时机IV

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

思路分析（子问题）：

状态机的变化：多了一个参数j表示我们最多可以交易几笔

在加减prices[i]的时候进行j-1，表示我们进行了一笔交易，那剩下在递归的时候最多只能交易j-1次

注意：j-1只在加prices[i]或者减prices[i]的时候写一次，加表示我们卖出，可以看做一次交易，减表示一次买进，也可以看做一次交易，但是加减prices[i]的时候都写，就说明我们买进一次再卖出算成了两次交易，这样就错了

笔者觉得在卖出的时候进行交易次数的计算比较好，就使用这个

递归边界部分，和前两道题不同的就是j如果小于0了那肯定就是不合法的状态，因为我们的交易次数最少应该是0，所以就返回一个负无穷表示这是不合法的

1.回溯 DFS

1.返回值和参数

i是每天的价格

status是状态，表示是否持有股票

j是我们现在最多可以交易多少笔

dfs返回值是我们在前i天持有或者不持有股票，在最多交易j次的前提下可以获得的最大利润

int dfs(int i,int j,int status,vector<int>& prices)

2.终止条件

就是在前两题的基础上了一个不合法的状态，那就是交易次数小于0的话要返回负无穷

注意判断的顺序，交易次数j一定要先判断，因为只要j小于0那肯定是不合法的

		if(j<0)
            return INT_MIN;
        if(i<0)
            if(status==1) 
                return INT_MIN;
            else
                return 0;

3.本层逻辑

在我们加prices[i]的时候，就说明是卖出股票，就说明第i天进行了一次交易，第i天的利润是prices[i]，那前i-1天的利润就是在最多交易j-1笔的情况下的最大利润，传入j-1

		if(status==1)
            return max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);
        else
            return max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)+prices[i]);

完整代码：

当然，这是超时的

class Solution {
public:
    int dfs(int i,int j,int status,vector<int>& prices)
    {
        if(j<0)
            return INT_MIN;
        if(i<0)
            if(status==1) 
                return INT_MIN;
            else
                return 0;
        if(status==1)
            return max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);
        else
            return max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)+prices[i]);
    }
    int maxProfit(int k,vector<int>& prices) {
        return dfs(prices.size()-1,k,0,prices);
    }
};

2.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

class Solution {
public:
    int dfs(int i,int j,int status,vector<int>& prices,vector<vector<vector<int>>>& dp)
    {
        if(j<0)
            return INT_MIN;
        if(i<0)
            if(status==1) 
                return INT_MIN;
            else
                return 0;
        if(dp[i][j][status]!=-1)
            return dp[i][j][status];
        if(status==1)
            return dp[i][j][status]=max(dfs(i-1,j,1,prices,dp),dfs(i-1,j,0,prices,dp)-prices[i]);
        else
            return dp[i][j][status]=max(dfs(i-1,j,0,prices,dp),dfs(i-1,j-1,1,prices,dp)+prices[i]);
    }
    int maxProfit(int k,vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(k+1,vector<int>(2,-1)));
        return dfs(prices.size()-1,k,0,prices,dp);
    }
};

//lambda
class Solution {
public:
    int maxProfit(int k,vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size(),vector<vector<int>>(k+1,vector<int>(2,-1)));
        function<int(int,int,int)> dfs=[&](int i,int j,int status)->int{
            if(j<0)
            return INT_MIN;
            if(i<0)
                if(status==1) 
                    return INT_MIN;
                else
                    return 0;
            if(dp[i][j][status]!=-1)
                return dp[i][j][status];
            if(status==1)
                return dp[i][j][status]=max(dfs(i-1,j,1),dfs(i-1,j,0)-prices[i]);
            else
                return dp[i][j][status]=max(dfs(i-1,j,0),dfs(i-1,j-1,1)+prices[i]);
        };
        return dfs(prices.size()-1,k,0);
    }
};

3.1:1翻译为动态规划

1.确定dp数组以及下标的含义

dfs换成dp就是数组以及下标含义

2.确定递推公式

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

3.dp数组如何初始化(难理解的点)

1.第一维度prices.size()+1是我们的数组下标表示天数的i从1开始

2.表示交易次数的j初始化是k+2的大小是因为

-1,0,1,2，…，k一共是k+2个状态，这一点和递归里面的对应

3.对应递归的终止条件，j必须大于0才是合法的，其他的都是不合法的，所以一开始初始化都是负无穷(除以2是为了防止溢出)

然后单独把j大于0，并且是第0天（对应i<0的if），也不持有股票(对应的是递归里的if（status==0)）都赋值为0，表示这种情况下没有利润

vector<vector<vector<int>>> dp(prices.size()+1,
                               vector<vector<int>>(k+2,
                                                   vector<int>(2,INT_MIN/2)));
for(int i=1;i<=k+1;i++)
	dp[0][i][0]=0;

4.确定遍历顺序

后续结果需要依赖前面的计算结果，故使用从前往后遍历

		for(int i=0;i<prices.size();i++)
        {
            for(int j=1;j<=k+1;j++)
            {
                dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-1][1]+prices[i]);
                dp[i+1][j][1]=max(dp[i][j][1],dp[i][j][0]-prices[i]);
            }
        }

完整代码

class Solution {
public:
    int maxProfit(int k,vector<int>& prices) {
        vector<vector<vector<int>>> dp(prices.size()+1,vector<vector<int>>(k+2,vector<int>(2,INT_MIN/2)));
        for(int i=1;i<=k+1;i++)
            dp[0][i][0]=0;
        for(int i=0;i<prices.size();i++)
        {
            for(int j=1;j<=k+1;j++)
            {
                dp[i+1][j][0]=max(dp[i][j][0],dp[i][j-1][1]+prices[i]);
                dp[i+1][j][1]=max(dp[i][j][1],dp[i][j][0]-prices[i]);
            }
        }
        return dp[prices.size()][k+1][0];
    }
};

4.滚动数组优化

和01背包一样，前面都是i后面都是i-1

由于j要靠j-1推出来，所以需要从后往前遍历j

class Solution {
public:
    int maxProfit(int k,vector<int>& prices) {
        vector<vector<int>> dp(k+2,vector<int>(2,INT_MIN/2));
        for(int i=1;i<=k+1;i++)
            dp[i][0]=0;
        for(int i=0;i<prices.size();i++)
        {
            for(int j=k+1;j>=1;j--)
            {
                dp[j][0]=max(dp[j][0],dp[j-1][1]+prices[i]);
                dp[j][1]=max(dp[j][1],dp[j][0]-prices[i]);
            }
        }
        return dp[k+1][0];
    }
};