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