121. 买卖股票的最佳时机
1、贪心
把序列分成两个部分，那么左边的最小值和右边的最大值差值就是最优解。
class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""low_price = float('inf')len_price = len(prices)res = 0for i in range(len_price):low_price = min(prices[i], low_price) # 更新左边的最小值res = max(prices[i] - low_price, res) # 更新整体的最大差值return res2、动态规划
动态规划的思路来源是每一天的状态（利润持有量）是根据前一天的状态推算出来的/
1、确定dp数组的含义
类似于树dp，每一个节点有取和不取两种状态，也就是说，对于每一天的价格，都有“入手”和“出售”两种状态，此时dp是一个len*2的二维数组，每一个元素记录每一天的买入和卖出后的最优状态 。
2、确定递推公式
对于两种状态的dp数组，针对每一个可能的状态都有他的更新公式；
对于“当前持有股票”的状态（这里“持有”是指之前某一天到今天有买入记录后到状态）：
dp[i][0] = max(dp[i-1][0], -prices[i])，
也就是说，今天的“持有”状态的最优解是前一天“持有”状态的最优解和“在今天买入”的状态的最大值（之所以是-值是因为越大说明买的越值）。
对于“当前未持有”的状态：
dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0)，
也就是说，是前一天“未持有”股票的状态和今天卖出状态的最大值。
3、初始化
在（2、）的公式下，dp[i][0]都得是负数（取max操作），所以初始化dp[0][0] = -prices[0]，dp[0][1] = 其余dp = 0。
4、遍历顺序
由于状态是根据从前往后的时间顺序来更新，所以遍历的顺序是由大到小。
class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""dp = [[0] * 2] * len(prices)dp[0][0] = -prices[0]for i in range(1, len(prices)):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 max(dp[-1])对于初始化，其实是跟公式严格一致的。
例如，如果把dp[i][0]理解为一个负数值（取Max），则需要初始化为负数，并且在更新dp[i][1]的时候是prices[i]+dp[i][0]，因为卖出的状态是负数。
但是，如果想保持dp数组都是正的，则需要改写初始化和更新公式：
dp[0][0] = prices[0] dp[i][1] = max(dp[i-1][1], prices[i]-dp[i-1][0])并且最后返回值不再是max(dp[-1])，因为这样会导致如果无法卖出（应该输出0）的时候，反而在dp[-1][0]更新到最后一个数字的时候，由于>dp[-1][1] == 0，所以会被输出，这并无意义。
return dp[-1][1]122. 买卖股票的最佳时机 II
在前一道题的基础上，由于可以卖出多次，所以对于每一个（0时刻）之后的状态而言，都有可能有通过前两种状态上的买卖构成当前状态。因此对于i状态，有以下两种更新方式：
dp[i][0] = max(dp[i-1], dp[i-1][1] + prices[1]) // 多了一个i-1天的股票在i天买入的状态（上一题只是-prices[i]，因为只有买入的状态，之前都是0）
dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1]) // 跟之前的是一致的。
class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""dp = [[0] * 2] * len(prices)dp[0][0] = -prices[0]for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]) # 这里需要考虑可以卖出两次的情况，那么相应的当前持有股票也可能是昨天卖了又买的dp[i][1] = max(dp[i-1][0] + prices[i], dp[i-1][1])return max(dp[-1])123. 买卖股票的最佳时机 III
本题难点在于dp的定义和大小；以及更新的顺序。
如何在定义中体现出来题目的约束：最多两次。
1、dp的定义
和之前必须卖出两次不一样，本题的状态有5种：
（1）没有操作
（2）第一次买入
（3）第一次卖出
（4）第二次买入
（5）第二次卖出
2、递归公式
在原有基础上更新，每一次的状态都是基于上一次的前一个状态进行更新。
dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1])
dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])
dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])
dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])
3、初始化
0时刻的状态：
（1）0状态：0
（2）1状态：第一次买入0 - prices[0]
（3）2状态：第一次买入-prices[0] + prices[0] = 0
（4）3状态：第二次买入（这里还是按照0时刻的价格）：0 - prices[0]
（5）4状态：第二次卖出：-prices[0] + prices[0] = 0
综上，只有1和3状态需要更新初始化状态为-prices[0]
4、遍历顺序
i基于i-1更新，所以从前往后遍历。
class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""dp = [[0] * 5] * len(prices)"""5个状态：0-没有操作；1-第一次买入(基于0)；2-第一次卖出（基于1）；3-第二次买入（基于2）；4-第二次卖出（基于3）"""# 初始化dp[0][1] = -prices[0] # 第一次买入dp[0][3] = -prices[0] # 第二次买入"""卖出的没有修改，保持0:理解为当天买入卖出"""for i in range(1, len(prices)):dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) # 基于上一次没操作的状态dp[i][2] = max(dp[i-1][2], dp[i-1][1] + prices[i])dp[i][3] = max(dp[i-1][3], dp[i-1][2] - prices[i])dp[i][4] = max(dp[i-1][4], dp[i-1][3] + prices[i])return max(dp[-1])Day46结束！！！