【动态规划】简单多状态（二）

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/

优质解

思路：

• 本题的三状态怎么来的，本来是买（已卖） / 卖，但是本题多了一个冷冻期，限制的是当天买的行为，所以变成了三状态。已卖 + 可买 / 已卖 + 不可买 / 卖
• dp[i]：当天结束时，最大收益。当天结束后的状态又可以再细分（开 3 * n的数组）。
  • 持股dp[0]
  • dp[1]不持股且明天不可以买
  • dp[2]不持股且明天可以买
• 状态转移方程（当天结束的状态：由前一天状态和当天行为决定）：
  • 可变成持股状态的：
    • 前一天不持股且明天可以买 + 当天买入；
    • 前一天持股 + 当天不变
  • 可变成不持股且明天不可买的：
    • 前一天持股 + 当天卖出
  • 可变成不持股且明天可买的：
    • 前一天不持股且明天可买 + 当天不变；
    • 前一天不持股且明天不可买 + 当天不变
• 由上可推出方程
• dp[0][i] = max(dp[2][i - 1] - price[i], dp[0][i - 1])
• dp[1][i] = dp[0][i - 1] + price[i]
• dp[2][i] = max(dp[1][i - 1], dp[2][i - 1])
• 初始化：dp[0][0] = -price[0]，dp[1][0] = dp[2][0] = 0
• 填表顺序：三个一起填
• 返回值：max(dp[1][n - 1], dp[2][n - 1])

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

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

714. 买卖股票的最佳时机含手续费

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/

个人解

思路：

// dp[0][i] 第 i 天结束后为持股状态时的最大收益
// dp[1][i] 第 i 天结束后为不持股状态时的最大收益
// dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);
// dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);

不多说了，难度不如上一题
用时：10:00
屎山代码：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) 
    {
        int n = prices.size();
        vector<vector<int>> dp(2, vector(n, 0));
        dp[0][0] = -prices[0] - fee; // 让买入算手续费
        for(int i = 1; i < n; i++)
        {
            dp[0][i] = max(dp[1][i - 1] - prices[i] - fee, dp[0][i - 1]);
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1] + prices[i]);
        }
        return dp[1][n - 1];
    }
};

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

123. 买卖股票的最佳时机 III

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/

优质解

思路：

• 通过分析状态表示，我们发现必须要三维才能够很好的表示状态
• 第一维：持股 / 不持股，第二维：最大利润 ，第三维：所剩交易次数

但是我们也可以把持股和不持股分出来：

• f[i][j] : "持股"状态，第i天结束之后，完成了j次交易，的最大利润
• g[i][j] : "不持股"状态，第i天结束之后，完成了j次交易，的最大利润

可见，下标直接表示交易次数
我们规定，只有在卖出的时候，交易次数才++
则状态转移方程：

• f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])
• g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])

初始化（其实是解决越界行为）：

• 初始时，交易次数为 1 和 2 的初始化
  • 我们可以让f[0][1] = f[0][2] = - INT_MAX / 2，即：取最小值（比所有可能的结果都小），使得该位置不会被下一天max选到，从而不影响正常的状态转移（g同理）
  • /2的原因：因为g[i - 1][j] - prices[i]会导致负数溢出，所以控制一下
• f[i - 1][j - 1] + prices[i]的操作：j - 1会越界
  • 而这个式子中j等于0是无意义的，因为如果当天有卖出行为，则g[i][j]的j一定 >= 1
  • 因此，我们可以把式子变换成：

g[i][j] = g[i - 1][j];
if(j > 1)
	g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);

• 是从第1天开始填的，基于第0天，所以：f[0][0] = -p[0]、g[0][0] = 0

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -INT_MAX / 2));
        auto g = f;
        f[0][0] = -prices[0]; g[0][0] = 0;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j < 3; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        return max(max(g[n - 1][0], g[n - 1][1]), g[n - 1][2]);
    }
};

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

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

个人解

思路：

• 和上一题一样

用时：6:00
屎山代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(k + 1, -INT_MAX/2));
        auto g = f;
        f[0][0] = -prices[0];
        g[0][0] = 0;
        for(int i = 1; i < n; i++)
        {
            for(int j = 0; j <= k; j++)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if(j >= 1)
                    g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);
            }
        }
        int ans = 0;
        for(int i = 0; i <= k; i++)
                ans = max(ans, g[n - 1][i]);
        return ans;
    }
};

时间复杂度：$O(n\ast k)$
空间复杂度：$O(n\ast k)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！