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

121.买卖股票的最佳时机

代码随想录链接

题目

LeetCode-121.买卖股票的最佳时机

这道题老朋友了, 给定的数组价格是一支股票在一段日子每天的价格, 只能买入卖出一次, 求最大能获得的利润.

题目分析

动态规划是主要状态与状态之间的推算, 在这道题目中, 每一天可以看作有两种状态, 分别是持有股票和没有持有股票.

动态规划_五四部曲:

• 确定dp数组及下标含义

  dp[i][0]代表第i天不持有股票所获得的最多现金, dp[i][1]代表持有股票所获得的最多现金. 现金可以是负数.

• 确定递推公式

  每一天都有两个状态, 同样的这两个状态也可以从前面一天的两个状态计算而来.

  当前天的不持有, 也就是dp[i][0], 可以是前一天持有, 今天卖出, 也可以前一天一直不持有, 有:

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

  当前日子的持有, 也就是dp[i][1], 同样可以从前一天的状态推出来, 有:

  \[dp[i][1] = max(dp[i - 1][1], -prices[i])\]

  为什么是第二个只是\(-prices[i]\)呢? 因为本题目中买入卖出只能有一次.

• dp数组的初始化

  dp[0][0] 代表第一天不持有, 所以dp[0][0]必定为0; dp[0][1]代表第一天持有, dp[0][1]应初始化为\(-prices[0]\).

• 遍历顺序

  每天的状态都是由前一天决定的, 所以遍历顺序一定是从前往后.

题解

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

122.买卖股票的最佳时机II

代码随想录链接

题目

LeetCode-122.买卖股票的最佳时机II

在上面一题的基础上, 不限制买入卖出的次数, 甚至同一天先买入再卖出都可以.

题目分析

由于没有买入卖出的次数限制, 而其他逻辑都是一样的, 所以只需要将上面一题的分析中对于买入次数的限制取消掉即可, 即修改递推公式:

\[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])\]

题解

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