「代码随想录算法训练营」第三十五天 | 动态规划 part8

2024-08-12 17:50 由云雀AC了一整天发表于 #其他

121. 买卖股票的最佳时机

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
文章讲解：https://programmercarl.com/0121.买卖股票的最佳时机.html
题目难度：简单
视频讲解：https://www.bilibili.com/video/BV1Xe4y1u77q
题目状态：有一半的思路

思路一：贪心

对数组进行遍历，分别保存两个变量：最小的买入时间left，最大的获利金额ans，遍历完就得到答案了。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int left = INT_MAX;
        int ans = 0;
        for(int i = 0; i < prices.size(); ++i) {
            left = min(left, prices[i]);
            ans = max(ans, prices[i] - left);
        }
        return ans;
    }
};

思路二：动规

创建一个二维动规数组dp[i][]，其大小为vector<len, vector<int>(2)>。

dp[i][0]表示在第i天持有所花费的钱，此时并不一定是在i天买入的，也可能是在i-1天买入的，这个就是其动规的公式：dp[i][0] = max(dp[i - 1][0], -price[i])。
dp[i][1]表示在第i天整到的最多的钱，此时也并不一定必须在i天卖出，也可能是在i-1天卖出的，取决于谁获利最多，动规公式如下：dp[i][1] = max(price[i] + dp[i - 1][0], dp[i - 1][0])。

代码：

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

思路二代码改进：

由于dp[i][]只有dp[i - 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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
文章讲解：https://programmercarl.com/0122.买卖股票的最佳时机II（动态规划）.html
题目难度：中等
视频讲解：https://www.bilibili.com/video/BV1D24y1Q7Ls
题目状态：有一半的思路

思路一：贪心

这题在学习贪心算法的时候做过，只需要遍历数组，然后将具有正收益的盈利金额加起来。

代码：

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

思路二：动态规划

这里和上一题一样，也要维持一个二维动规数组，但有一个地方需要改变，就是在dp[i][0]的计算上，上一题因为只能进行一次交易，所以dp[i][0]要么是dp[i - 1][0]（在第i天之前已经进行买入），要么是-price[i]（在当天买入）。但这道题中，我们可以进行多次交易，因此dp[i][0]要么是dp[i - 1][0]（在第i天之前进行买入），要么是dp[i - 1][1] - price[i]（在当天进行买入，我们要将之前的收益也要加进来）。
要始终记得：dp[i][0]表示第i天持有股票的最大利润；dp[i][1]表示第i天不持有股票的最大利润。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 0) return 0;
        vector<vector<int>> dp(len, vector<int>(2));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; ++i) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][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];
    }
};

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/
文章讲解：https://programmercarl.com/0123.买卖股票的最佳时机III.html
题目难度：困难
视频讲解：https://www.bilibili.com/video/BV1WG411K7AR
题目状态：没思路

思路：

这次的动规数组主要维护的是五个状态：

无操作
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

dp[i][j]中i表示第i天，j就是上面五个状态，dp[i][j]表示第i天状态j的所剩最大现金。

因此：每个状态就会有两种操作：

有操作：假设是状态1，那么就表示当天买入股票了，则dp[i][1] = dp[i - 1][0] - prices[i]。
没操作：就是这天没进行买入操作，那么dp[i][1] = dp[i - 1][1]。

其他状态同上。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len == 0) return 0;
        vector<vector<int>> dp(len, vector<int>(5));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for(int i = 1; i < len; ++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[len - 1][4];
    }
};