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

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
题目状态:没思路

思路:

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

  1. 无操作
  2. 第一次持有股票
  3. 第一次不持有股票
  4. 第二次持有股票
  5. 第二次不持有股票

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];
    }
};

热门相关:隐婚101天:唐少宠妻成瘾   国民校草求抱抱   超级融合   呆萌配腹黑:绝宠小冤家   呆萌小萝莉:高冷男神太腹黑