代码随想录算法训练营第51天 |309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

发布于 2023-03-28  620 次阅读


AI 摘要

Excerpt: This article presents the solutions to two algorithm problems from LeetCode: "309. Best Time to Buy and Sell Stock with Cooldown" and "714. Best Time to Buy and Sell Stock with Transaction Fee". Both solutions use dynamic programming to determine the best time to buy or sell stocks under various conditions. The article provides explanations for determining the dp array and its indices, the recurrence relation, initializing the dp array, and iterating through the array. The author also presents optimized versions of the solutions to reduce space complexity.

309. 最佳买卖股票时机含冷冻期 - 力扣(Leetcode)

思路:

  • 使用动态规划

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

      • dp[i][j]的定义为:
        • dp[i][0]的意思是今日保持股票买入的状态
        • dp[i][1]的意思是今日保持股票卖出的状态
        • dp[i][2]的意思是今日卖出股票
        • dp[i][3]的意思是今日在股票购买冷却状态中
    2. 确定递推公式

      // 状态转移方程
      // dp[i][0]有三种操作
      // 第一种是昨天就已经买入了
      // 第二种是昨天是股票卖出的状态
      // 第三种是昨天是股票在购买冷却的状态,要取三种状态的最大值
      dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1] - prices[i]), dp[i - 1][3] - prices[i]);
      // dp[i][1]有两种操作
      // 第一种是昨天就保持股票卖出的状态
      // 第二种是昨天是股票冷却期
      dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
      // dp[i][2]只有一种操作,就是今天卖出了股票
      dp[i][2] = dp[i - 1][0] + prices[i];
      // dp[i][3]也只有一种操作,就是昨天卖出了股票
      dp[i][3] = dp[i - 1][2];
    3. dp数组如何初始化

      vector< vector<int> > dp(len, vector<int>(4, 0));
      // 只需要初始化第一天买入为-prices[0]
      dp[0][0] = -prices[0];
      // 其他都初始化为0
    4. 确定遍历顺序

      // 因为 i = 0 已经初始化,所以从 i = 1 开始

我的AC代码

高空间复杂度

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector< vector<int> > dp(len, vector<int>(4, 0));
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; ++i) {
            dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1] - prices[i]), dp[i - 1][3] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[len - 1][1], max(dp[len - 1][2], dp[len - 1][3]));
    }
};

优化空间复杂度

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector< vector<int> > dp(2, vector<int>(4, 0));
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; ++i) {
            dp[i % 2][0] = max(max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]), dp[(i - 1) % 2][3] - prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][3]);
            dp[i % 2][2] = dp[(i - 1) % 2][0] + prices[i];
            dp[i % 2][3] = dp[(i - 1) % 2][2];
        }
        return max(dp[(len - 1) % 2][1], max(dp[(len - 1) % 2][2], dp[(len - 1) % 2][3]));
    }
};

标准答案

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
    }
};

714. 买卖股票的最佳时机含手续费 - 力扣(Leetcode)

思路:

  • 使用动态规划

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

      • dp[i]的定义为:
        • dp[0]的意思是持有股票的最大现金
        • dp[1]的意思是不持有股票的最大现金
    2. 确定递推公式

      // 状态转移方程
      // dp[0]有两种操作
      // 第一种是昨天已经持有股票了
      // 第二种是今天购买股票,要算上手续费
      dp[0] = max(dp[0], dp[1] - prices[i] - fee);
      // dp[1]有两种操作
      // 第一种是昨天已经不持有股票了
      // 第二种是今天卖出股票
      dp[1] = max(dp[1], dp[0] + prices[i]);
    3. dp数组如何初始化

      vector<int> dp(2, 0);
      // 只需要初始化持有股票的状态
      dp[0] = -prices[0] - fee;
      // 不持有股票的状态默认初始化为0
    4. 确定遍历顺序

      因为已经初始化 i = 0 了,所以从 i = 1 开始

我的AC代码

/*
  其实只需要一维数组就能解决问题,我们分情况来看。如果是dp[1],那么有两种操作,一种是昨天就已经买了股票,保持原样,那么其实可以直接和自己比,即dp[0] = dp[0];还有一种操作是今天买股票,那么就要继承dp[1],即手上没有股票时的金额,然后减去prices[i]和fee,因为dp[0]的语句顺序在dp[1]前面,所以此时的dp[1]就是昨天的dp[1],所以可以直接用,那么dp[0]的状态转移方程就写成了dp[0] = max(dp[0], dp[1] - prices[i] - fee);,对于dp[1]来说也是同理,一种操作是和昨天一样手上没有股票,那么就和自己比,即dp[1] = dp[1],还有一种就是今天把股票卖了,所以要继承dp[0]的情况,dp[0]无非就两种,一种是之前就买了股票,所以do[1]这边就相当于之前买了股票,今天卖了,另一种情况是dp[0]今天买了股票,那么dp[1]今天再把股票卖掉,就相当于今天买今天卖,代码逻辑上 也是通顺的,无非是今天买今天卖多次一举。所以dp[1]的状态转移方程就写成dp[1] = max(dp[1], dp[0] + prices[i]);
*/

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        vector<int> dp(2, 0);
        dp[0] = -prices[0] - fee;
        for(int i = 1; i < prices.size(); ++i) {
            dp[0] = max(dp[0], dp[1] - prices[i] - fee);
            dp[1] = max(dp[1], dp[0] + prices[i]);
        }
        return dp[1];
    }
};

滚动数组

//之所以可以使用滚动数组是因为递推公式只依赖前一天的结果,所以只需要保存两天即可

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int len = prices.size();
        vector< vector<int> > dp(2, vector<int>(2, 0));
        dp[0][0] = -prices[0] - fee;
        for(int i = 1; i < len; ++i) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i] - fee);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);
        }
        return dp[(len - 1) % 2][1];
    }
};

标准答案

// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};