【代码随想录】刷题笔记Day48

前言

早上练车去了（好久没有8点前醒了），练科目二两小时下来脚根可真酸啊，希望下周一把过。练完顺带去Apple西湖免费换新了耳机，羊毛爽！

121. 买卖股票的最佳时机 - 力扣（LeetCode）

贪心法

更新最小值，更新最大区间利润值

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

动规法（一维）

一维思路和贪心类似，有点难理解
dp[i]含义
- 以prices[i]价格卖出可获得的最大利润
递推公式
- 情况一：i-1买入，i卖出，收益prices[i] - prices[i-1]
- 情况二：i-1之前已卖出，如果延迟到i卖出，取更高的收益
- dp[i] = max(prices[i] - prices[i-1], prices[i] - prices[i-1] + dp[i-1]);
初始化及顺序
- dp[0] = 0，从前往后
要最高收益，结果取dp[i]的最大值（和其他一维有差别），另外可以优化一下空间

// 优化前
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<int> dp(len);int result = 0;for(int i = 1; i < len; i++){dp[i] = max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] + dp[i - 1]);result = max(result, dp[i]);}return result;}
};// 优化后
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();int dp0 = 0, dp1 = 0;  // 只需要维护滚动两个值int result = 0;for(int i = 1; i < len; i++){dp1 = max(prices[i] - prices[i - 1], prices[i] - prices[i - 1] + dp0);result = max(result, dp1);dp0 = dp1; // 互换}return result;}
};

动规法（二维）
- 二维用的01双状态，类似打家劫舍III
- dp数组含义
  - dp[i][0] 表示第i天持有股票所得最多现金：维持现状 + 买入股票
  - dp[i][1] 表示第i天不持有股票所得最多现金：维持现状 + 卖出股票
- 递推公式
  - dp[i][0] = max(dp[i - 1][0], -prices[i]);
  - dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
- 初始化及顺序
  - dp[0][0] = -prices[0]; dp[0][1] = 0; 从前往后
- 答案取dp[max][1]，因为不持有一定比持有多
- ```
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[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];}
};
```