leetcode系列(一)：买卖股票

1. 第一题：122. 买卖股票的最佳时机 II

按照我自己的渐进思路写出四种方法，前三种都是动态规划，最后一种是贪心。

方法1：二维动态矩阵

思路是维护一个n*2的动态矩阵，dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润。那么则有转移方程如下：

• 第i天持有股票的最大利润 = max（保持i-1天持有股票， i-1天不持有股票 + 今天买入）
• 第i天不持有股票的最大利润 = max（保持i-1天不持有股票， i-1天持有股票 + 今天卖出） 

写出公式就是：

代码如下：

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp =[[0 for i in range(2)] for j in range(n)]
        dp[0][1] = -prices[0]  #买入(持有)
        dp[0][0] = 0    #手上没有股票(不持有)
        for i in range(1,n):
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        return dp[-1][0]

 python的提交结果：

 方法2：两个一维动态矩阵

转移方程是一样的，代码如下：

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy =  [0] * n
        free = [0] * n 
        buy[0] = -prices[0]#买入
        for i in range(1,n):
            buy[i] = max(buy[i-1], free[i-1] - prices[i])
            free[i] = max(free[i-1], buy[i-1] + prices[i])
        return free[-1]

 提交结果，速度有所提升

 方法3：取消数组

通过方法2可以看到，第i次的结果只与i-1次有关，与前面的无关，因此我们可以只保留前一次的记过即可。

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy =  -prices[0]
        free = 0 
        for i in range(1,n):
            buy = max(buy, free - prices[i])
            free = max(free, buy + prices[i])
        return free

我们看一下代码，buy = max(buy, free - prices[i])先更新的，free是后更新的。正常来说更新free用到的是前一天的buy，如果buy先更新的话，那么free更新所用的就不是前一天的buy，而是今天的buy。之所以这样没有问题，是因为同一天可以买入再卖出

 方法4：贪心

贪心的方法可以这么理解，我们要求最大利润，就必然要使得卖出的价格高于买入的价格，即prices[latest] > prices[pre]。我们遍历的最小单元跨度为1，即就是对于相邻的区间1，如果prices[i+1] > prices[i]，我们就可以买入卖出获利。

这样做的依据同样是：同一天可以买入再卖出。

我们是想一个场景，第一天的价格为7，第二天的价格为1，显然我们不能在第一天买入，在第二天卖出，会亏本的，所以应该在第二天买入。如果以第一天买入的起始，那么实际上第二天买入就= 一天买入并卖出 + 第二天买入。

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        profit = 0
        for i in range(1,n):
            profit += max(0, prices[i] - prices[i-1])
        return profit

 2. 第二题：121. 买卖股票的最佳时机

这一题比上一题稍微简单一点，因为只允许买卖一次，并且不能在同一天买入卖出。

方法1：暴力穷举

嵌套两个循环，速度较慢

方法2：二维动态矩阵

思路是维护一个n*2的动态矩阵，dp[i][0]表示第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润。那么则有转移方程如下：

• 第i天持有股票的最大利润 = max（保持i-1天持有股票，今天第一次买入）
• 第i天不持有股票的最大利润 = max（保持i-1天不持有股票， i-1天持有股票 + 今天卖出） 

红色字体也是与上一题转移方程不同的地方，原因是只能买一次。

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0 for j in range(2)] for i in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0] #持有
        for i in range(1,n):
            dp[i][1] = max(dp[i-1][1],-prices[i]) #第一次买
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) #卖出去
        return dp[-1][0]

方法3：两个一维动态矩阵

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy = [0] * n 
        sell = [0] * n 
        buy[0] = -prices[0]
        for i in range(1,n):
            buy[i]= max(buy[i-1],-prices[i]) #第一次买
            sell[i] = max(sell[i-1], buy[i-1] + prices[i]) #卖出去
        return sell[-1]

方法4：取消数组

    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy = -prices[0]
        sell = 0
        for i in range(1,n):
            buy= max(buy,-prices[i]) #第一次
            sell = max(sell, buy + prices[i]) #卖出去
        return sell