leetCode 121.买卖股票的最佳时机 动态规划 + 状态转移

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

// 第i天 dp[i][0]持有股票时最大现金   dp[i][1]不持有股票时最大现金
 
// dp[i][0]        dp[i-1][0]
//                 0 - prices[i]
 
// dp[i][1]        dp[i-1][1]
//                 dp[i-1][0] + prices[i]

>>思考和分析

>>动规五部曲

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

• dp[i][0] 表示第 i 天持有股票所得最多现金，持有股票之后哪来现金呢？这是因为一开始现金是0，那么加入第 i 天买入股票现金就是 -prices[i]，这是一个负数
• dp[i][1] 表示第 i 天不持有股票所得最多现金

"持有" : 不代表就是当天"买入"！可能昨天就买入了，今天保持有的状态

2.确定递推公式

① 若第 i 天持有股票即 dp[i][0],那么可以由两个状态推出来

• 第 i - 1 天就持有股票，那么就保持现状，昨天持有股票的所得现金就是现在所得，即：   
  • dp[i - 1][0]
• 第 i 天买入股票，买入今天的股票后所得现金就是现在所得,即：
  • -prices[i]

dp[i][0]应该选所得现金最大的，dp[i][0] = max(dp[i - 1][0],-prices[i]);

② 若第 i 天不持有股票即 dp[i][1],也可以由两个状态推出来

• 第 i - 1天就不持有股票，那么就保持现状，昨天不持有股票的所得现金就是现在所得，
  • dp[i-1][1]
• 第 i 天卖出股票，按照今天股票价格卖出后所得现金就是现在所得，即：                         
  • dp[i - 1][0] + prices[i]

dp[i][1]应该选所得现金最大的，dp[i][1] = max(dp[i - 1][1],dp[i - 1][0] + prices[i]);

3.dp数组初始化

由递推公式

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

其基础都是要从 dp[0][0] 和 dp[0][1] 推导出来

• dp[0][0] -= prices[0];
• dp[0][1] = 0;

4.确定遍历顺序

从递推公式可以看出 dp[i] 都是由 dp[i - 1] 推导出来的，那么一定是 从前向后 遍历

5.举例推导dp数组

class Solution {
public:
    // 动态规划 时间复杂度；O(n) 空间复杂度：O(n)
    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(dp[i - 1][1],dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

>>优化空间复杂度

我们分析递推公式，可以看出dp[i] 只是依赖于 dp[i - 1] 的状态

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

那只需要记录当前天的 dp状态 和 前一天的 dp状态就可以了，可以使用滚动数组来节省空间

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

• 时间复杂度：O(n)
• 空间复杂度：O(1)

>>贪心算法思路

由于股票只买卖一次，因此贪心的思路就是找到最左最小值，最右最大值，得到的差值就是最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

参考和推荐文章、视频

 代码随想录 (programmercarl.com)

 动态规划之 LeetCode：121.买卖股票的最佳时机1_哔哩哔哩_bilibili

来自代码随想录的课堂截图：