【Description】
給定一個整數(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
解釋: 能夠達(dá)到的最大利潤:
在此處買入 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.
【Idea】
動規(guī)的題每次思路都非常的妙，[菜狗點頭.jpg]
借鑒了官方來說蹦肴，動規(guī)解法滿足“子最優(yōu)解” 的特性
順序遍歷難以避免僚碎，每次遍歷元素拆解為買/賣的兩個動作，因此用滿倉full/ 空倉emp來標(biāo)記當(dāng)前位置下的最大利潤（子問題）阴幌，每次按照買or不買勺阐， 賣or不賣的分支進行更新
買：需空倉才能買，用前一次賣掉的最大利潤 - 當(dāng)前減倉需要的成本矛双；
賣：需滿倉才能賣渊抽，用前一次持倉的最大利潤 + 落袋為安的本利 - 賣出手續(xù)費
（我可真是個理財小能手
因為是拿空間換時間，所以空間復(fù)雜度消耗難以避免
【Solution】
class Solution:
def maxProfit(self, prices: List[int], fee: int) -> int:
# 一道動態(tài)規(guī)劃
emp, full = 0, -prices[0]
for i in range(len(prices)):
emp = max(emp, full+prices[i]-fee)
full = max(full, emp-prices[i])
return max(emp, full)
