給定一個整數(shù)數(shù)組 prices秋秤，其中第 i 個元素代表了第 i 天的股票價格 介衔；非負整數(shù) fee 代表了交易股票的手續(xù)費用恨胚。
你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費炎咖。如果你已經(jīng)購買了一個股票赃泡，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值乘盼。
注意：這里的一筆交易指買入持有并賣出股票的整個過程升熊，每筆交易你只需要為支付一次手續(xù)費。
示例 1:
輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
思路：
1.確定狀態(tài) 某一天的狀態(tài)分為兩種一種dp[i][0]代表該天交易后不持有股票绸栅，dp[i][1]代表該天交易后持有股票
2.狀態(tài)轉(zhuǎn)移方程
--第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]
不持有股票,需要買入股票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天賣出股票利潤最大
4.計算順序--順序計算
n = len(prices)
# 定義一個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]
買股票最佳時機
給定一個整數(shù)數(shù)組 prices 蓖柔，它的第 i 個元素 prices[i] 是一支給定的股票在第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤风纠。你最多可以完成 k 筆交易况鸣。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1：
輸入：k = 2, prices = [2,4,1]
輸出：2
解釋：在第 1 天 (股票價格 = 2) 的時候買入竹观，在第 2 天 (股票價格 = 4) 的時候賣出镐捧，這筆交易所能獲得利潤 = 4-2 = 2 。
示例 2：
輸入：k = 2, prices = [3,2,6,5,0,3]
輸出：7
解釋：在第 2 天 (股票價格 = 2) 的時候買入臭增，在第 3 天 (股票價格 = 6) 的時候賣出, 這筆交易所能獲得利潤 = 6-2 = 4 懂酱。
隨后，在第 5 天 (股票價格 = 0) 的時候買入誊抛，在第 6 天 (股票價格 = 3) 的時候賣出, 這筆交易所能獲得利潤 = 3-0 = 3
1.確定狀態(tài)
buy[i][j]代表第i天恰好j筆交易列牺，手中持有股票；
sell[i][j]代表第i天恰好進行j筆交易芍锚，手中沒有股票
根據(jù)是否是第i天買入的分為兩種情況
--不是第i天買入的
--是第i天買入的并且恰好進行了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è)置為負無窮
sell[0][1...k] = 非法可設(shè)置為負無窮
進行0筆交易時,第i天開始買股票
buy[i][0] = max(buy[i-1][0],sell[i-1][j]-prices[i])
優(yōu)化n個股票最多進行n/2次交易
if not prices:
return 0
n = len(prices)
k = min(k,n//2)
# 開辟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])
``
