代码随想录算法训练营第49天 | 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

TFTree 发布于 2023-03-27 638 次阅读

AI 摘要

Excerpt: The article discusses the solutions to problems 121. Best Time to Buy and Sell Stock and 122. Best Time to Buy and Sell Stock II on LeetCode. For problem 121, a simple greedy algorithm and a dynamic programming approach are presented, while for problem 122, only a dynamic programming approach is discussed. The article provides the thought process behind each approach, including the definition of the dp states and the recurrence relations used to update them. It also includes sample code for each solution.

121. 买卖股票的最佳时机 - 力扣（Leetcode）

思路:

  • 最简单的想法，使用贪心算法，记录到某一天为止(包括那一天)的最便宜的股票价格，然后与今日作差，差值最大的即为答案

  • 动态规划做法

    • dp[i]的含义:dp[i][0]代表持有股票此时现金的最大值，dp[i][1]代表不持有股票此时现金的最大值,使用滚动数组来分别代表今天和前一天持有和不持有股票时现金的最大值

    • 递推公式

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

    • 初始化

      • ``` c++
        vector<int> dp(2, 0);
        dp[0] = -prices[0];

我的AC代码

贪心算法

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

动态规划

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(2, 0);
        dp[0] = -prices[0];
        for(int i = 1; i < prices.size(); ++i) {
            dp[0] = max(dp[0], -prices[i]);
            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 len = prices.size();
        vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
        }
        return dp[(len - 1) % 2][1];
    }
};

122. 买卖股票的最佳时机 II - 力扣（Leetcode）

思路:

  • 使用动态规划

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

      • dp[i]的含义:dp[i][0]代表持有股票此时现金的最大值，dp[i][1]代表不持有股票此时现金的最大值,使用滚动数组来分别代表今天和前一天持有和不持有股票时现金的最大值

    2. 确定递推公式

      // 状态转移方程
// 和上一题不同的是,购买股票时的初始资金不再总是为0，而是dp[i - 1][1]
// 即上一次不持有股票所剩余的资金值
// 所以dp[i][0]的状态转移方程是
// dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
// 因为此处采用滚动数组节约空间复杂度
// 故最终方程为dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], dp[(i - 1) % 2][0] + prices[i]);

    3. dp数组如何初始化

      // 只需要建立一个2 x 2的滚动数组即可
// 因为状态转移方程只依赖上一次的状态
// dp[0][0] = -prices[0]即一开始就购买股票
// dp[0][1] = 0,因为刚开始不持有股票现金就是0
// 在初始化vector的时候已经将所有值都置为0
// 故不需要重复置dp[0][1] = 0
vector< vector<int> > dp(2, vector<int>(2, 0));
dp[0][0] = -prices[0];

    4. 确定遍历顺序

      // 从前往后遍历，因为i = 0已经初始化，故从i = 1开始

我的AC代码

// 时间复杂度O(n),空间复杂度O(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector< vector<int> > dp(2, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; ++i) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
            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(1)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i % 2][0] = max(dp[(i - 1) % 2][0], dp[(i - 1) % 2][1] - prices[i]);
            dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
        }
        return dp[(len - 1) % 2][1];
    }
};