LeetCode 121. 買賣股票的最佳時機 LeetCode 122. 買賣股票的最佳時機II LeetCode 123.買賣股票的最佳時機III

LeetCode 121. 買賣股票的最佳時機

嘗試一：暴力解決方法

常用兩個指針去遍歷prices數組，dp[i]用于記錄在第i天所獲得的最大利潤。時間復雜度是O(N^2)，超出時間限制。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 買入賣出的次數 <= 1## 1. dp數組定義。## dp[i] 表示第i天前所獲得的最大利潤## 2. dp初始化dp = [0] * (len(prices))## 3. 遞推公式## 利潤： diff = price[j] - price[i]## 第j天的利潤大于等第i天利潤，那么第j天利潤 = 第i天利潤 + 第j天價格 - 第i天價格## dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])## 4. 遍歷順序for i in range(len(prices)):for j in range(i+1, len(prices)):if prices[j] > prices[i]:dp[j] = max(dp[j], dp[i] + prices[j] - prices[i])## 5. 打印dp數組return max(dp)

動規的思路：

1. dp數組定義：第i天時，我目前的狀態有兩種，一種是持有股票，另外一種是已賣出股票，因此dp數組是一個二維數組，第一維用來表示天數，第二維用來表示在這一天我目前手頭的股票狀態。因此，dp[i][0]表示為?天數<= i?時我已購入一只股票， dp[i][1]表示為天數 <= i?時?我已賣出一只股票后所獲得的最大利潤。

2. dp數組初始化：?由于遞推公式是前面推后面，因此第一個元素需要初始化。

dp[0][0] = -prices[0]:?第0天持有購買，是消費行為。為什么是-prices[0]，其實是因為現有手頭現金為0，因此是0-prices[0]，結果就是-prices[0]
dp[0][1] = 0:?第0天賣出股票沒有利潤可言。
另外，由于dp[i][0]是針對負數求最大化，因此dp數組要用負無窮去初始化，再對特殊值進行初始化。

3. 遞推公式：

dp[i][0]的情況有兩種：第i天前已購買(dp[i-1][0]) /?第?i?天時才購買( 現有金額 -prices[i],?負號表示購買，是虧損了這么多錢，而本題只有買賣一次，因此現有金額是0)，為獲得最大利潤，我要盡可能以低的價格購入股票，因此dp[i][0] =?max(dp[i-1][0], -prices[i])
相應地，dp[i][1]的情況也有兩種：第i天前已賣出(dp[i-1][1]) /?第?i?天時才賣出（利潤 = prices[i] - dp[i-1][0] (第i天前買入的股票才可以在第i天時賣出) ），那最大利潤遞推公式就是dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) 。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""# 1. dp數組定義。由于第i天的現有股票有兩種狀態，一個是已買入，一個是已賣出，因此需要用一個長度為2的數組來表示這種關系
# dp[i][0], 表示第i天已買入股票的狀態，這種狀態描述了我在第i天前（包括第i天）購入了一只股票，值表示我購入這支股票所花的錢
# dp[i][1], 表示第i天已賣出股票的狀態，這種狀態描述了我在第i天前（包括第i天）賣出了一只股票，值表示我賣出這支股票所花的錢dp = [[-float('inf')] * 2 for _ in range(len(prices))]# 2. dp初始化dp[0][0] = -prices[0]dp[0][1] = 0# 3. 遞推公式# dp[i][0] = max(dp[i-1][0], -prices[i])# dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])  # dp[i-1][0]+prices[i]表示第i天賣出時得到的利潤# 4. 遍歷順序for i in range(len(prices)):dp[i][0] = max(dp[i-1][0], -prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i])# 5. 打印dp數組if dp[-1][1] < 0:    ## 表示虧損了，那還不如不買return 0return dp[-1][1]

LeetCode 122.買賣股票的最佳時機II

思路一：貪心算法

只要有正利潤就貪下來

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 思路一：可以用貪心思路解決dp = [0] * len(prices)for i in range(1, len(prices)):margin = prices[i] - prices[i-1]if margin > 0:dp[i] = marginall_margin = sum(dp)return all_margin

思路二：動態規劃

思路：

與第一題相比關鍵在于可以買賣多次，那第一題只能買賣一次，因此起始資金始終為0。而可以買賣多次的話，你在后續賺到錢后到起始資金就不是0了，因此這是與上道題的最大區別。

遞推公式：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])

dp[i][0] = dp[i-1][0]，第i天不買入股票。
dp[i][0] = dp[i-1][1] - prices[i]，第i天買入股票，那現在就需要起始金額-購買股票金額了，起始金額為之前賺到的利潤dp[i-1][1]。

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])

dp[i][1] ?= dp[i-1][1]，第i天不賣出股票。
dp[i][1] = dp[i-1][0] + prices[i]，第i天賣出股票，那就需要在之前買入股票的剩余錢的基礎上 + 賣出這只股票所得到的錢。

總結：dp[i][0]表示我在第i天前（包括第i天）買入股票后手頭上的錢，dp[i][1]表示我在第i天前（包括第i天）賣出股票后所獲得的總利潤。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""## 思路二：動態規劃# 1. dp數組定義dp = [ [float("-inf")]*2 for _ in range(len(prices)) ]# 2. dp初始化dp[0][0] = -prices[0]       ##  起始資金為0dp[0][1] = 0# 3. 遞推公式# dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])# dp[i][1] = max(dp[i][0], dp[i-1][1] + prices[i])# 4. 遍歷順序for i in range(1, len(prices)):dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])# 5. 打印dp# print(dp)return dp[-1][1]

LeetCode 123.買賣股票的最佳時機III

買賣股票的最佳時機Ⅰ是只能進行一筆交易

買賣股票的最佳時機Ⅱ是可以進行多筆交易

這道題是兩筆交易，如果設置一個count來計算交易的次數，從左向右交易一次就count+1

但這種做法會陷入你前面兩筆交易雖賺了，但并不是全局的最優。

思路：

為什么這道題要涉及到用多個狀態來進行描述，主要影響因素在于交易次數的限制，多筆交易也可以采用多種狀態來進行描述，但是由于不知道具體交易的次數，因此可以只有兩個狀態來進行買入和賣出的操作，并且這個買入和賣出可以繼承之前已交易后的狀態。
本題是兩次交易，一次交易有兩個狀態，分別是買入和賣出，因此兩次交易要通過4個狀態進行描述，后面的狀態依賴于前面的狀態。

1. dp數組定義

dp[i][0]: 在第i天前（包括第i天）不進行股票的買入和賣出操作 ?（這個狀態可以不要）
dp[i][1]: ..., 第一次持有股票
dp[i][2]: ..., 第一次賣出股票
dp[i][3]: ..., 第二次持有股票
dp[i][4]: ..., 第二次賣出股票
可以看到1,2?是用來衡量第一筆交易的狀態，3,4是用來衡量第二筆交易的狀態

2. dp初始化

dp[0][0] = 0，? ? ? ? ? ? ?表示在第一天不進行任何操作
dp[0][1] = -prices[0]，表示在第一天第一次買入股票
dp[0][2] = 0，? ? ? ? ? ? ?表示在第一天第一次賣出股票
dp[0][3] = -prices[0]，?表示在第一天第二次買入股票
dp[0][4] = 0，? ? ? ? ? ? ? 表示在第一天第二次賣出股票

3. 遞推公式

dp[i][0] = dp[i-1][0]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 表示延續之前的不操作狀態
dp[i][1] = max(dp[i-1][1], -prices[i])

dp[i][1] = dp[i-1][1],? 第一次操作，表示不買入股票，此時延續第i天之前買入股票后的狀態；

dp[i][1] = -prices[i]，第一次操作，表示買入股票，此時起始金額為0，因此是 0 -?prices[i]

dp[i][2] = max(dp[i-1][2], prices[i]+dp[i-1][1])

dp[i][2] = dp[i-1][2],?? 第一次操作，表示不賣出股票，此時延續第i天之前不賣出股票后的狀態；

dp[i][2] = prices[i]+dp[i][1]，第一次操作，表示賣出股票，此時賣出所得prices[i] +?之前持有股票的狀態dp[i-1][1]?就得到了凈利潤

dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])

dp[i][3] = dp[i-1][3],?? 第二次操作，表示買入股票，此時延續第i天之前不買入股票后的狀態；

dp[i][3] = -prices[i]+dp[i-1][2]，第二次操作，表示買入股票，此時起始金額為dp[i-1][2]，因此是 dp[i-1][2] -?prices[i]

dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])

dp[i][4] = dp[i-1][4],?? 第二次操作，表示不賣出股票，此時延續第i天之前不賣出股票后的狀態；

dp[i][4] = prices[i]+dp[i-1][1]，第二次操作，表示賣出股票，此時賣出所得prices[i] +?之前持有股票的狀態dp[i-1][3]?就得到了兩次交易后得到的凈利潤。

Code

class Solution(object):def maxProfit(self, prices):""":type prices: List[int]:rtype: int"""# 1. dp數組定義：# 由于一共是兩筆交易，因此買入賣出的次數是4次，因此需要通過4個狀態來衡量這兩筆交易# dp[i][0]: 在第i天前（包括第i天）不進行股票的買入和賣出操作  （這個狀態可以不要）# dp[i][1]: ..., 第一次持有股票# dp[i][2]: ..., 第一次賣出股票# dp[i][3]: ..., 第二次持有股票# dp[i][4]: ..., 第二次賣出股票# 可以看到1,2 用來衡量第一筆交易的狀態，3,4用來衡量第二筆交易的狀態dp = [[float('-inf')]*5 for _ in range(len(prices))]# 2. dp數組初始化dp[0][0] = 0dp[0][1] = -prices[0]dp[0][2] = 0dp[0][3] = -prices[0]dp[0][4] = 0# 3. 遞推公式# dp[i][0] = dp[i-1][0]# dp[i][1] = max(dp[i-1][1], -prices[i])# dp[i][2] = max(dp[i-1][2], prices[i]+dp[i][1])# dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])# dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])# 4.遍歷順序for i in range(1, len(prices)):dp[i][0] = dp[i-1][0]        dp[i][1] = max(dp[i-1][1], -prices[i])dp[i][2] = max(dp[i-1][2], prices[i]+dp[i-1][1])dp[i][3] = max(dp[i-1][3], -prices[i]+dp[i-1][2])dp[i][4] = max(dp[i-1][4], prices[i]+dp[i-1][3])# 5. 打印dp數組# print(dp)return dp[-1][4]

另外，可以看到dp[i][0]的這個定義是不起作用的，因此實際可以只定義4個狀態，沒必要多定義一個不進行任何操作的狀態。