解題思路參考buladong解題，詳細信息可以關注該公眾號。

1.動態規劃框架

動態規劃–解決買賣k問題，k取不同的值，團滅：
LeetCode-121 一次買賣
LeetCode-122 不限次數
LeetCode-309 不限次數+冷凍期
LeetCode-714 不限次數+手續費
LeetCode-123 兩次買賣
LeetCode-188 k次買賣

LeetCode-188 k次買賣-給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 k 筆交易。注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

利用動態規劃來解決問題，確定每一天有多少可能的狀態，再找出狀態對應的選擇。

每天選擇可能有三種：買入，賣出，無操作。但是，三種選擇的發生是有條件的。（賣出操作的前提是你持有股票）

每天的狀態變量有3個：天數，允許交易的最大次數，當前的持有狀態(持有股票1/未持有0)。三維數組可以裝下所有狀態。
$dp[i][k][0or1]$, 到第i天，最多進行k次，手上持有/未持有股票，獲得的最多利潤。
要求解的是$dp[n?1][K][0]$的值。

k 買入算是一次操作，收益一開始是0，一次買賣：買入時0-買入時價格，賣出時：0-買入時價格+賣出時價格

狀態轉移方程：
$$dp[i][k][0]=max(dp[i?1][k][0],dp[i?1][k][1]+prices[i])$$
今天未持有：昨天未持有/昨天持有賣掉
$$dp[i][k][1]=max(dp[i?1][k][1],dp[i?1][k?1][0]?prices[i])$$
今天持有：昨天持有/昨天持有賣掉

初始狀態base case：
未開始未持有，收益為0：$dp[?1][k][0]=0$
未開始以持有，不可能，收益為負無窮：max 的時候取不到$dp[?1][k][1]=?\infty$
允許的最大交易次數為0，未持有無收益：$dp[i][0][0]=0$
允許的最大交易次數為0，持有不可能設為負無窮：$dp[i][0][1]=?\infty$

用這個思路來解決 以上的題

LeetCode-121 一次買賣

k =1

# dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i])
# dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0]-prices[i]),dp[i-1][0][0] =0
# k = 1 不可以變，因此上面狀態變量減少為兩個
# dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
# dp[i][1] = max(dp[i-1][1], 0-prices[i]),		dp[i-1][0][0] =0
# dp[i][1]的更新會影響dp[i+1][0]的更新def maxProfit(self, prices):n = len(prices)if n == 0 :return 0dp=[[0,0] for i in range(n)]for i in range(0,n):if i == 0:dp[0][0] = 0dp[0][1] = -prices[0]else:dp[i][0] =  max(dp[i-1][0], dp[i-1][1]+prices[i])dp[i][1] =  max(dp[i-1][1], 0-prices[i])   # dp[i-1][0]未持有收益為0return dp[n-1][0]

LeetCode-122 不限次數

$k=\infty$

# dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
# dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
# k =  \infty k-1 = k  k 狀態又可以去除
# 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]),		dp[i-1][0]為進行了很多次操作用于的收益
# dp[i][1]的更新會影響dp[i+1][0]的更新
def maxProfit(self, prices):n = len(prices)if n == 0:return 0dp = [[0,0] for i in range(n)]for i in range(n):if i == 0:dp[0][0] = 0dp[0][1] = -prices[0]else: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[n-1][0]

LeetCode-309 不限次數+冷凍期

賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。

# dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
# dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i]),		前兩天賣出操作今天買入    
# 初始值得設定上
def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""n = len(prices)if n == 0:return 0dp = [[0,0] for i in range(n)]for i in range(n):if i == 0:dp[0][0] = 0dp[0][1] = -prices[0]elif i == 1:dp[1][0] = max(dp[0][0], dp[0][1] + prices[1])dp[1][1] = max(dp[0][1], dp[0][0] - prices[1])else:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])return dp[n-1][0]

LeetCode-714 不限次數+手續費

給定一個整數數組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負整數 fee 代表了交易股票的手續費用。
你可以無限次地完成交易，但是你每筆交易都需要付手續費。如果你已經購買了一個股票，在賣出它之前你就不能再繼續購買股票了。
返回獲得利潤的最大值。
注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續費。

每筆交易減去一個手續費即可，在買入的時候多減掉一個手續費，相當于股票的買入價格提高了

    def maxProfit(self, prices, fee):""":type prices: List[int]:type fee: int:rtype: int"""n = len(prices)if n == 0:return 0dp = [[0,0] for i in range(n)]for i in range(n):if i == 0:dp[0][0] = 0dp[0][1] = -prices[0]-fee   # 注意這個值else:dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-

LeetCode-123 兩次買賣

k = 2需要考慮狀態，唯一的區別就是base case 設定

# dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
# dp[i][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]),		   
# 需要遍歷k,最多進行兩次，當然我也可以不買賣
def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""k = 2       # 注意k 要能取得到n = len(prices)if n == 0:return 0dp=[[[0,0] for j in range(k+1)] for i in range(n)]for i in range(n):for j in range(k+1):if i == 0 or j ==0:dp[i][j][0] = 0dp[i][j][1] = -prices[0]     # 通用初始化else:dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])return dp[n-1][k][0] 

LeetCode-188 k次買賣

k取任意確定的數字時，解題框架于=與k = 2 時一致。當k 過大時，會造超內存錯誤。根據買賣至少需要兩天，可以限制最大交易次數不應該超過n/2,如果超過了就相當于k = 無窮的情況。整合一下前面的方法即可。

class Solution(object):def maxProfit(self, k, prices):""":type k: int:type prices: List[int]:rtype: int"""n = len(prices)if n == 0:return 0if k > n//2:dp = [[0,0] for i in range(n)]for i in range(n):if i == 0:dp[0][0] = 0dp[0][1] = -prices[0]else: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[n-1][0]else:dp=[[[0,0] for j in range(k+1)] for i in range(n)]for i in range(n):for j in range(k+1):if i == 0 or j == 0:dp[i][j][0] = 0dp[i][j][1] = -prices[0]else:dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])return dp[n-1][k][0]

2.貪心特解

這兩種特殊情況還是特殊解來的快，框架反而繁雜。

LeetCode-121 一次買賣

關鍵找到每一天之前的最低價格，兩者相減，求增益最大。

def maxProfit(self, prices):n = len(prices)if n == 0:return 0min_val = prices[0]res = 0for i in range(1,n):res = max(res, prices[i]-min_val)min_val = min(min_val, prices[i])return res

LeetCode-122 不限次數

不限次數，每一個谷底買入下一個峰值賣出，多次操作，和值最大。累加收益。

def maxProfit(self, prices):n = len(prices)if n == 0:return 0res = 0 for i in range(1,n):if prices[i]>prices[i-1]:res += prices[i]-prices[i-1]return res