給定一個(gè)整數(shù)數(shù)組 prices，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。
你可以無(wú)限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購(gòu)買(mǎi)了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購(gòu)買(mǎi)股票了。
返回獲得利潤(rùn)的最大值。
注意：這里的一筆交易指買(mǎi)入持有并賣出股票的整個(gè)過(guò)程，每筆交易你只需要為支付一次手續(xù)費(fèi)。
示例 1:
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達(dá)到的最大利潤(rùn):  
在此處買(mǎi)入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買(mǎi)入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤(rùn): ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

思路：
1.確定狀態(tài) 某一天的狀態(tài)分為兩種一種dp[i][0]代表該天交易后不持有股票，dp[i][1]代表該天交易后持有股票
2.狀態(tài)轉(zhuǎn)移方程
--第i天沒(méi)有股票，其狀態(tài)由第i-1天持有股票和第i-1天不持有股票
持有股票dp[i-1][1]+prices[i]-fee
不持有股票dp[i-1][0]
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]-fee)
--第i天有股票，其狀態(tài)由第i-1天持有股票和第i-1天不持有股票
持有股票dp[i-1][1]
不持有股票,需要買(mǎi)入股票dp[i-1][0]- prices[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
3.邊界條件
第0天[0,-prices[0]]，第n-1天賣出股票利潤(rùn)最大
4.計(jì)算順序--順序計(jì)算

n = len(prices)
# 定義一個(gè)n行2列的數(shù)組
dp = [[0, -prices[0]]] + [[0, 0] for _ in range(n - 1)]
for i in range(1, n):
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee)
    dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
return dp[n - 1][0]

買(mǎi)股票最佳時(shí)機(jī)

給定一個(gè)整數(shù)數(shù)組 prices ，它的第 i 個(gè)元素 prices[i] 是一支給定的股票在第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 k 筆交易。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。
示例 1：
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 2 天 (股票價(jià)格 = 4) 的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價(jià)格 = 2) 的時(shí)候買(mǎi)入，在第 3 天 (股票價(jià)格 = 6) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-2 = 4 。
隨后，在第 5 天 (股票價(jià)格 = 0) 的時(shí)候買(mǎi)入，在第 6 天 (股票價(jià)格 = 3) 的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 3-0 = 3 

1.確定狀態(tài)
buy[i][j]代表第i天恰好j筆交易，手中持有股票；
sell[i][j]代表第i天恰好進(jìn)行j筆交易，手中沒(méi)有股票
根據(jù)是否是第i天買(mǎi)入的分為兩種情況
--不是第i天買(mǎi)入的
--是第i天買(mǎi)入的并且恰好進(jìn)行了j筆交易
2.狀態(tài)轉(zhuǎn)移方程
buy[i][j] = max(buy[i-1][j],sell[i-1][j]-prices[i])
sell[i][j] = max(sell[i-1][j],buy[i-1][j-1]+prices[i])
3.確定邊界條件
第0天持有股票為buy[0][0]=-prices[0]
第0天不持有股票為sell[0][0] = 0
buy[0][1...k] = 非法可設(shè)置為負(fù)無(wú)窮
sell[0][1...k] = 非法可設(shè)置為負(fù)無(wú)窮
進(jìn)行0筆交易時(shí),第i天開(kāi)始買(mǎi)股票
buy[i][0] = max(buy[i-1][0],sell[i-1][j]-prices[i])
優(yōu)化n個(gè)股票最多進(jìn)行n/2次交易

if not prices:
    return 0
n = len(prices)
k = min(k,n//2)
# 開(kāi)辟k+1 的數(shù)組
buy = [[0]*(k+1) for _ in range(n)]
sell = [[0]*(k+1) for _ in range(n)]
# 初始化
buy[0][0],0= -prices[0],sell[0][0]
for i in range(1,k+1):
    buy[0][i] =sell[0][i]= float("-inf")
for i in range(1,n):
    buy[i][0] = max(buy[i-1][0],sell[i-1][0]-prices[i])
    for j in range(1,k+1):
        buy[i][j] = max(buy[i-1][j],sell[i-1][j]-prices[i])
        sell[i][j] = max(sell[i-1][j],buy[i-1][j-1]+prices[i])

return max(sell[n-1])
``