问题描述：【Math、DP】121. Best Time to Buy and Sell Stock
解题思路：
方法1（数学理解）：对于单次买入单次卖出股票问题，实际上是求后面一个数减去前面一个数的最大差值。因此，在遍历一遍的过程中，只需要维护一个最小值，和当前利润的最大值即可。时间复杂度 O(n)，空间复杂度 O(1)。
该问题的一般形式为： 求 A[j] - A[i] 的最大值，对于 j > i。
该问题的解决方式为：让 min_ 指向最小值 A[i]；在遍历的过程中更新 A[j] - min_ 的最大值。
Python3 实现：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0:
return 0
min_ = prices[0]
ans = 0
for i in range(1, len(prices)):
ans = max(ans, prices[i] - min_)
min_ = min(min_, prices[i])
return ans
方法2（DP）：此题目和最大子段和 Leetcode 【53】给一个数组，求最大子段和 类似。
- 创建一个 dp[len(prices)]，其中 dp[i] 表示前 i 天的利润；
- 类似于最大字段和问题，容易找到转移方程
dp[i] = max(0, dp[i-1] + prices[i] - prices[i-1])，其中 0 表示利润出现负值时，这一天不买股票； - max(dp) 就是最后的答案。
时间复杂度 O(n)，空间复杂度 O(n)（实际上空间复杂度也可以降为 O(1)，因为只用到前一天的结果）。
Python3 实现：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0:
return 0
dp = [0] * len(prices)
for i in range(1, len(prices)):
dp[i] = max(0, prices[i] - prices[i-1] + dp[i-1])
return max(dp)
问题描述：【Greedy、DP、Math】122. Best Time to Buy and Sell Stock II
解题思路：
方法1（Greedy）：对于多次买入多次卖出股票问题，实际上是只要后面的数比前面的数大，就累加利润即可。这是一种贪心的思想。时间复杂度 O(n)，空间复杂度 O(1)。
Python3 实现：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
ans = 0 # 最大利润
for i in range(len(prices) - 1):
if prices[i+1] > prices[i]:
ans += prices[i+1] - prices[i] # 累加利润
return ans
方法2（DP）：当然，我们也可以使用动态规划求解。
- 创建一个 dp[len(prices)]，其中 dp[i] 表示前 i 天的最大利润；
- 容易找到转移方程
dp[i] = (dp[i-1] + prices[i] - prices[i-1]) if (prices[i] > prices[i-1]) else dp[i-1]； - dp[-1] 就是最后的答案。
时间复杂度 O(n)，空间复杂度 O(n)（实际上空间复杂度也可以降为 O(1)，因为只用到前一天的结果）。
Python3 实现：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0:
return 0
dp = [0] * len(prices)
for i in range(1, len(prices)):
dp[i] = (dp[i-1] + prices[i] - prices[i-1]) if (prices[i] > prices[i-1]) else dp[i-1]
return dp[-1]
方法3（数学理解）：
该问题的一般形式为： 将 A 划分为不重叠的 N 段，求这N 段 ∑ (A[j] - A[i]) 的最大值；每一段都有 j > i。
该问题的解决方式为：让 min_ 指向最小值 A[i]；在遍历的过程中，如果 A[j] > min_，则累加 A[j] - min_，同时更新 min_ 为 A[j]；否则，更新 min_ 为 min_ 和 A[j] 中的较小者。
Python3 实现：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) == 0:
return 0
ans = 0
min_ = prices[0] # 第一个数为最小值
for i in range(1, len(prices)):
if prices[i] > min_: # 可以卖股票
ans += prices[i] - min_
min_ = prices[i]
else: # 不能卖股票
min_ = min(min_, prices[i])
return ans
问题描述：【多状态DP、Math】714. Best Time to Buy and Sell Stock with Transaction Fee
解题思路：
方法1（双DP）：比起 Leetcode 122，这里多了一个买卖股票需要扣除费用。对于第 i 天来说，手中要么没有股票，要么手持一只股票。因此，可以采取两个 DP 数组，记录第 i 天持有股票或者第 i 天不持有股票的最大收益。
- 用 nohold 表示第 i 天不持有股票的收益，hold 表示第 i 天持有一只股票的收益；
-
未持有股票的情况：要么是前一天就没有股票，要么是今天卖掉了，所以这种情况下，未持有股票的最大收益就是这两者的最大值，即
nohold[i] = max(nohold[i-1], hold[i-1] + price[i] - fee)； -
持有一只股票的情况：要么是前一天就持有股票，要么是今天刚好买了一只股票，取其中最大值，即
hold[i] = max(hold[i-1], nohold[i-1] - price[i])； - 初始化
nohold[0] = 0，hold[0] = -prices[0]。最后，nohold[-1] 就是答案（因为最后手里肯定没有股票，hold 实际上是一个辅助数组，帮助计算 nohold 的）。
Python3 实现：
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
hold = [0] * len(prices)
nohold = [0] * len(prices)
hold[0] = -prices[0]
for i in range(1, len(prices)):
nohold[i] = max(nohold[i-1], hold[i-1] + prices[i] - fee)
hold[i] = max(hold[i-1], nohold[i-1] - prices[i])
return nohold[-1]
方法2（数学理解）：比起 Leetcode 122 的方法 3，这里对目标多了一项 -fee，方法类似。
该问题的一般形式为： 将 A 划分为不重叠的 N 段，求这N 段 ∑ (A[j] - A[i] - fee) 的最大值；每一段都有 j > i。
该问题的解决方式为：先将目标变形，得到求 N 段 ∑ ((A[j] - fee) - A[i]) 的最大值，即把 A[j] - fee 看成一个整体。这样，就能使用 Leetcode 122 的方法 3 的类似解法。让 min_ 指向最小值 A[i]；在遍历的过程中，如果 (A[j] - fee) > min_，则累加 (A[j] - fee) - min_，同时更新 min_ 为 (A[j] - fee)；否则，更新 min_ 为 min_ 和 A[j] 中的较小者（这里不需要将 A[j] 替换成 A[j] - fee 的原因是不能卖股票，所以不用减去 fee）。
Python3 实现：
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
ans = 0
min_ = prices[0] # 第一个数为最小值
for i in range(1, len(prices)):
if prices[i] - fee > min_: # 可以卖股票
ans += prices[i] - fee - min_
min_ = prices[i] - fee
else: # 不能卖股票，不用将 prices[j] 减去 fee
min_ = min(min_, prices[i])
return ans
问题描述：【多状态DP】309. Best Time to Buy and Sell Stock with Cooldown
解题思路：
方法1（双状态DP）：这道题和 Leetcode 714 思想相同，只不过由于增加了一个冻结期（cooldown），导致状态转移方程有所区别。
- 仍然用 nohold 表示第 i 天不持有股票的收益，hold 表示第 i 天持有一只股票的收益；
-
未持有股票的情况：要么是前一天就没有股票，要么是今天卖掉了，即
nohold[i] = max(nohold[i-1], hold[i-1] + price[i])； -
持有一只股票的情况：要么是前一天就持有股票，要么是今天刚好买了一只股票，但是注意：如果是今天刚好买了股票，则昨天必须休息（因为有一天的cooldown），那么买股票应该依赖于前天（而不是昨天）的未持有股票的状态，即
hold[i] = max(hold[i-1], nohold[i-2] - price[i])； - 初始化
nohold[0] = 0，hold[0] = -prices[0]，hold[1] = max(hold[0], -prices[1])，。最后，nohold[-1] 就是答案（因为最后手里肯定没有股票，hold 实际上是一个辅助数组，帮助计算 nohold 的）。
Python3 实现：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
nohold = [0] * len(prices)
hold = [0] * len(prices)
hold[0] = -prices[0]
for i in range(1, len(prices)):
nohold[i] = max(nohold[i-1], hold[i-1] + prices[i])
hold[i] = max(hold[i-1], nohold[i-2] - prices[i]) if i >= 2 else max(hold[i-1], -prices[i])
return nohold[-1]
方法2（三状态DP）：方法1 划分成有股票和无股票两个状态，由于 cooldown 的存在，还可以将无股票状态再细分成两个不相交的状态（第 i 天休息和第 i 天卖出），因此我们得到以下三个状态：
- s0[i]：第 i 天休息（未持有股票），包括 cooldown；
- s1[i]：第 i 天持有股票；
- s2[i]：第 i 天卖出股票。
-
s0[i] = max(s0[i-1], s2[i-1])，前一天也休息或前一天刚卖出股票； -
s1[i] = max(s1[i-1], s0[i-1] - prices[i])，前一天也持有或前一天休息； -
s2[i] = s1[i-1] + prices，前一天持有。
注意：
- 初始化
s0[0] = 0，s1[0] = -prices[0]，s2[0] = 0； - 最大利润应该是未持有股票的情况，因此结果应该是
max(s0[-1], s2[-1])。
Python3 实现：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
s0 = [0] * len(prices)
s1 = [0] * len(prices)
s2 = [0] * len(prices)
s1[0] = -prices[0]
for i in range(1, len(prices)):
s0[i] = max(s0[i-1], s2[i-1])
s1[i] = max(s1[i-1], s0[i-1] - prices[i])
s2[i] = s1[i-1] + prices[i]
return max(s0[-1], s2[-1])
