代码随想录算法训练营第50天 |123.买卖股票的最佳时机III、188.买卖股票的最佳时机IV

发布于 2023-03-27  665 次阅读

AI 摘要

本文分享了力扣算法训练营第50天的学习笔记，包括了算法题“买卖股票的最佳时机III”和“买卖股票的最佳时机IV”的思路、动态规划方程和dp数组的初始化等内容。文章提供了三份不同版本的代码，分别实现了不同的空间复杂度和便于理解的程度，读者可根据自身情况选择适合的版本进行参考。

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

思路:

  • 使用动态规划

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

      • dp[i][j]的定义为：dp[i][0]没有意义，仅用于占位，dp[i][1]代表第一次持有股票的现金最大值，dp[i][2]代表第一次不持有股票的现金最大值，dp[i][3]代表第二次持有股票的现金最大值，dp[i][4]代表第二次不持有股票的现金最大值

    2. 确定递推公式

      // 状态转移方程
// dp[i][1]有两种状态，一种是本身就持有，那么值从dp[i - 1][1]演变而来
// 另一种是本身不持有，要购买一支股票，那么值就是-prices[i]，取两者最大值
dp[i % 2][1] = max(dp[(i - 1) % 2][1], -prices[i]);
// dp[i][2]有两种状态，一种是本身就不持有，那么值从dp[i - 1][2]演变而来
// 另一种是今天卖了手上的股票，那么值就是dp[i - 1][1] + prices[i]，取两者最大值
dp[i % 2][2] = max(dp[(i - 1) % 2][2], dp[(i - 1) % 2][1] + prices[i]);
// dp[i][3]有两种状态，一种是本身就持有，那么值从dp[i - 1][3]演变而来
// 另一种是本身不持有，要购买一支股票，但是此时的值要继承第一次不持有股票的值
// 所以此时的值就是dp[i - 1][2] - prices[i]
dp[i % 2][3] = max(dp[(i - 1) % 2][3], dp[(i - 1) % 2][2] - prices[i]);
// dp[i][4]有两种状态，一种是本身就不持有，那么值从dp[i - 1][4]演变而来
// 另一种是今天卖了手上的股票，那么值就是dp[i - 1][3] + prices[i]，取两者最大值
dp[i % 2][4] = max(dp[(i - 1) % 2][4], dp[(i - 1) % 2][3] + prices[i]);

    3. dp数组如何初始化

      vector< vector<int> > dp(2, vector<int>(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];

    4. 确定遍历顺序

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

我的AC代码

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

标准答案

空间复杂度高但便于理解

// 时间复杂度O(n),空间复杂度O(n)
// 这个版本空间复杂度高，但是便于理解
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size() - 1][4];
    }
};

空间复杂度低但不易于理解

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

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

思路:

  • 使用动态规划，这道题和123. 买卖股票的最佳时机 III - 力扣（Leetcode）的最大区别就是最大交易次数不同，本题最大交易次数是k次，而123. 买卖股票的最佳时机 III - 力扣（Leetcode）最大交易次数是固定的2次，写上一题的时候我就在想有没有可能会出一道题让交易次数可变，没想到还真有，理清逻辑，掌握交易背后的本质是写出这道题的关键

  • 我们用时间复杂度较高但较好理解的解法来做解析

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

      • dp[i][j]的定义为：dp[i][0]没有意义，仅用于占位，dp[i][k * 2 + 1]代表第k + 1次持有股票的现金最大值，dp[i][k * 2 + 2]代表第k + 1次不持有股票的现金最大值

    2. 确定递推公式

      // 状态转移方程
for(int j = 1; j <= k * 2; ++j) {
// dp[i][j](j为单数)有两种状态，一种是本身就持有，那么值从dp[i - 1][j]演变而来
// 另一种是本身不持有，要购买一支股票，其值要从上一次卖出股票那里继承
// 如果是第一次买股票就是从dp[i][0]那里继承
// 那么值就是dp[i - 1][j - 1] - prices[i]，取两者最大值
    if(j % 2 == 1) {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
    }
// dp[i][j](j为双数)有两种状态，一种是本身就不持有，那么值从dp[i - 1][j]演变而来
// 另一种是卖了手上的股票，其值要从上一次持有股票那里继承
// 那么值就是dp[i - 1][j - 1] + prices[i]，取两者最大值
    else {
        dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
    }
}

    3. dp数组如何初始化

      vector< vector<int> > dp(prices.size(), vector<int>(k * 2 + 1, 0));
for(int i = 1; i <= k * 2; ++i) {
    if(i % 2 == 1) {
        dp[0][i] = -prices[0];
    }
}

    4. 确定遍历顺序

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

我的AC代码

空间复杂度高

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

优化空间复杂度

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

标准答案

// 时间复杂度O(n * k),空间复杂度O(n * k)
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {

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