題目
難度：★★★★☆
類型：數(shù)組
方法：動(dòng)態(tài)規(guī)劃瓶蝴，分類討論
給定一個(gè)整數(shù)數(shù)組嚼黔，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 代箭。?
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤羡铲。在滿足以下約束條件下嫩与，你可以盡可能地完成更多的交易（多次買賣一支股票）:
你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）寝姿。
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)蕴纳。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出]
解答
建立dp矩陣会油，矩陣的維度為n行3列，其中：
dp[i][0]表示第i天持有股票的情況下的當(dāng)前收益古毛。
dp[i][1]表示第i天處于未持有股票翻翩，但是處于冷凍期狀態(tài)下的當(dāng)前收益；
dp[i][2]表示第i天處于未持有股票稻薇，也不在冷凍期狀態(tài)下的當(dāng)前收益嫂冻。
逐行（天）計(jì)算這三個(gè)狀態(tài)的數(shù)值，當(dāng)天買入記為負(fù)收益塞椎，當(dāng)天賣出記為正收益桨仿。
初始情況：
dp[0][0] = -prices[0]，第一天買入案狠，當(dāng)前累計(jì)收益為負(fù)值服傍，數(shù)值上是第一天的價(jià)格钱雷。
dp[0][1] = dp[0][2]=0，第一天未持有股票吹零，當(dāng)前累計(jì)收益為零罩抗。
遞推公式：
第i天持有（或買入）股票，這一天的累計(jì)收益值有兩種情況：
第一灿椅，這一天之前已經(jīng)持有股票套蒂，則對(duì)應(yīng)的收益為dp[i-1][0]；
第二茫蛹，這一天之前（前一天）處于非冷凍期的未持有股票狀態(tài)操刀，但是這一天買入，對(duì)應(yīng)的累計(jì)收益為dp[i-1][2] - prices[i]
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])第i天處于冷凍期婴洼，說明在這一天賣出了股票(這里有點(diǎn)費(fèi)解)骨坑。
dp[i][1] = dp[i-1][0] + prices[i]第i天處于非冷凍期未持有股票狀態(tài)，說明前一天沒有做任何操作柬采。
dp[i][2] = max(dp[i-1][1], dp[i-1][2]])
class Solution:
def maxProfit(self, prices):
if not prices:
return 0
n = len(prices)
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0][0] = - prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
return max(dp[n-1][1], dp[n-1][2])
如有疑問或建議卡啰，歡迎評(píng)論區(qū)留言~
