題目

難度：★★★☆☆
類型：數(shù)組
方法：動(dòng)態(tài)規(guī)劃

力扣鏈接請(qǐng)移步本題傳送門
更多力扣中等題的解決方案請(qǐng)移步力扣中等題目錄

給定一個(gè)整數(shù)數(shù)組 prices，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 ；非負(fù)整數(shù) fee 代表了交易股票的手續(xù)費(fèi)用。

你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費(fèi)。如果你已經(jīng)購買了一個(gè)股票，在賣出它之前你就不能再繼續(xù)購買股票了。

返回獲得利潤(rùn)的最大值。

注意：這里的一筆交易指買入持有并賣出股票的整個(gè)過程，每筆交易你只需要為支付一次手續(xù)費(fèi)。

示例 1:

輸入: prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出: 8
解釋: 能夠達(dá)到的最大利潤(rùn):
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤(rùn): ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:

0 < prices.length <= 50000.
0 < prices[i] < 50000.
0 <= fee < 50000.

解答

一維數(shù)組類的問題常用動(dòng)態(tài)規(guī)劃解決。

【定義數(shù)組】
由于狀態(tài)轉(zhuǎn)移時(shí)只需要用到上一個(gè)狀態(tài)，因此可以把一維的數(shù)組壓縮成零維，定義變量cash和hold，用于表示當(dāng)前尚未持有股票和當(dāng)前持有股票狀態(tài)下的累計(jì)最大收益。

【初始狀態(tài)】
第一天尚未持有股票狀態(tài)，當(dāng)前累計(jì)收益為零，記為cash=0；
第一天持有股票。當(dāng)前累計(jì)收益為-price[0]，記為hold=-price[0]；

【狀態(tài)轉(zhuǎn)移】
對(duì)于之后的每一天：
如果這一天是沒有持有股票的狀態(tài)，那么可能是因?yàn)椋?br> （1）最近幾天都沒有持有股票，這時(shí)累計(jì)收益繼承cash；
（2）剛剛賣出這一天的股票，這時(shí)累計(jì)收益為hold + prices[i] - fee；
從以上兩者中選取最大值，更新當(dāng)前cash變量。
如果這一天是持有股票狀態(tài)，可能的原因?yàn)椋?br> （1）最近幾天都持有這一股票，當(dāng)前累計(jì)收益繼承hold；
（2）剛剛買入這一天的股票，這時(shí)累計(jì)收益為cash - price[i]；
從以上兩者中選取最大值，更新當(dāng)前的hold變量。

【最終狀態(tài)】
最后，我們返回cash的值即可，因?yàn)榻刂習(xí)r刻股票一定是賣出的。

我們可以發(fā)現(xiàn)，這道動(dòng)態(tài)規(guī)劃題的特點(diǎn)是，我們定義了兩個(gè)狀態(tài)，兩個(gè)狀態(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

如有疑問或建議，歡迎評(píng)論區(qū)留言~

有關(guān)更多力扣中等題的python解決方案，請(qǐng)移步力扣中等題解析