【算法训练营day49】LeetCode121. 买卖股票的最佳时机 LeetCode122. 买卖股票的最佳时机II

标签：vector 买卖 股票 II 最佳时机 prices dp size

LeetCode121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

独上高楼，望尽天涯路

感觉贪心会更简单，动态规划反而搞复杂了对于这道题。

慕然回首，灯火阑珊处

第一次看题解还是挺难理解的，所以这次写的规范一点。

1. 确定dp数组及其下标的含义

dp[i][0]表示的是第i天持有股票所得最多现金，通俗一点，就是截止到第i天所能买入股票花费的最少现金。

dp[i][1]表示的是第i天不持有股票所得最多现金，通俗一点，就是截止到第i天卖出股票所赚得的最多现金。

截止是一个关键词，意思是不一定是第i天买入或卖出股票，而是包含第i天及之前所有时间的买入卖出操作。

2. 确定递推公式

dp[i][0]可以由两个状态推出来，一个是昨天及之前的买入价格更低；另一个是今天的买入价格更低；我们取最好的那个就行。

dp[i][1]也可以由两个状态推出来，一个是昨天及之前已经完成的买入卖出操作赚的更多；另一个是用今天的价格卖出，买入价格用昨天及之前最低的买入价格，赚的更多；我们还是取最好的那个就行。

3. dp数组如何初始化

dp[0][0]表示第0天最低的买入价格，只能是第0天的买入价格。

dp[0][1]表示第0天卖出所赚得的最多现金，因为第0天不能卖出，所以为0。

4. 确定遍历顺序

从前向后遍历prices数组即可。

5. 举例推导dp数组

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

---

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

题目链接：122. 买卖股票的最佳时机II

独上高楼，望尽天涯路

没什么思路。

慕然回首，灯火阑珊处

看完题解，猪脑过载，得慢慢消化...

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

标签：vector,买卖,股票,II,最佳时机,prices,dp,size
From： https://www.cnblogs.com/BarcelonaTong/p/17134988.html