題目
難度：★★★☆☆
類型：數(shù)組
方法：動態(tài)規(guī)劃
力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄
給定一個整數(shù)數(shù)組 prices，其中第 i 個元素代表了第 i 天的股票價格 ；非負(fù)整數(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.
注意:
0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.
解答
一維數(shù)組類的問題常用動態(tài)規(guī)劃解決。
【定義數(shù)組】
由于狀態(tài)轉(zhuǎn)移時只需要用到上一個狀態(tài)猜揪，因此可以把一維的數(shù)組壓縮成零維惭墓，定義變量cash和hold，用于表示當(dāng)前尚未持有股票和當(dāng)前持有股票狀態(tài)下的累計最大收益而姐。
【初始狀態(tài)】
第一天尚未持有股票狀態(tài)腊凶，當(dāng)前累計收益為零，記為cash=0毅人；
第一天持有股票吭狡。當(dāng)前累計收益為-price[0]，記為hold=-price[0]丈莺；
【狀態(tài)轉(zhuǎn)移】
對于之后的每一天：
如果這一天是沒有持有股票的狀態(tài)划煮，那么可能是因為：
（1）最近幾天都沒有持有股票，這時累計收益繼承cash缔俄；
（2）剛剛賣出這一天的股票弛秋，這時累計收益為hold + prices[i] - fee；
從以上兩者中選取最大值俐载，更新當(dāng)前cash變量蟹略。
如果這一天是持有股票狀態(tài)，可能的原因為：
（1）最近幾天都持有這一股票遏佣，當(dāng)前累計收益繼承hold挖炬；
（2）剛剛買入這一天的股票，這時累計收益為cash - price[i]状婶；
從以上兩者中選取最大值意敛，更新當(dāng)前的hold變量。
【最終狀態(tài)】
最后膛虫，我們返回cash的值即可草姻，因為截至?xí)r刻股票一定是賣出的。
我們可以發(fā)現(xiàn)稍刀，這道動態(tài)規(guī)劃題的特點是撩独，我們定義了兩個狀態(tài)，兩個狀態(tài)之間之間存在著信息交互账月。
class Solution(object):
def maxProfit(self, prices, fee):
cash, hold = 0, -prices[0]
for i in range(1, len(prices)):
cash = max(cash, hold + prices[i] - fee)
hold = max(hold, cash - prices[i])
return cash
如有疑問或建議综膀，歡迎評論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案，請移步力扣中等題解析
