代码随想录算法训练营Day49 | 动态规划(10/17) LeetCode 121. 买卖股票的最佳时机 122.买卖股票的最佳时机II

结束了打家劫舍问题，之前在练习贪心算法的时候做过LC122，现在用动态规划做一下LC121 和122。

第一题

121. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

这道题毫无疑问可以用贪心的方法解出来，不过既然练习到动态规划，当然是要应用动态规划五部曲了。

1. 确定dp数组（dp table）以及下标的含义
   1. dp[i][0] 表示第i天持有股票所得最多现金，其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。dp[i][1] 表示第i天不持有股票所得最多现金
2. 确定递推公式
   1. 如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
      1. 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
      2. 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]
   2. 那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);
   3. 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
      1. 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
      2. 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]
   4. 同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
3. dp数组如何初始化
   1. 由递推公式 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]和dp[0][1]推导出来。
   2. 那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
   3. dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;
4. 确定遍历顺序
   1. 从递推公式可以看出dp[i]都是由dp[i - 1]推导出来的，那么一定是从前向后遍历。
5. 举例推导dp数组

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if len == 0:
            return 0
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            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[-1][1]

第二题

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

和上一题的区别是，股票可以买卖多次了

因此在递推公式这一步，会和前面有区别。

 所以买入股票的时候，可能会有之前买卖的利润即：dp[i - 1][1]，所以dp[i - 1][1] - prices[i]。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        dp = [[0] * 2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        for i in range(1, length):
            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[-1][1]