從今天開始，我們會對「如何定義狀態」這件事情加以琢磨：畢竟不是所有的狀態都可以很直接地從「字串前綴」、「陣列索引」、「數列第 n 項」直接定義出來的。今天來說說演算法課本上的各種經典題目吧～

工作排程問題

題目是這樣的，有 N 項活動，其中第 i 項開始時間是 s[i]、結束時間是 f[i]。對於每一項活動，如果你全程參加它的話，可以獲得 v[i] 的成就點數。你沒有辦法在同一個時間點參加兩個活動，但是可以在一個活動結束的當下，立刻參與另一個剛開始的活動。請問最大的成就點數總和為何呢？

解題思考

我們可以依照逆向思考的思維，想像最後一個參加的活動開始與結束的區間為 [s, f]，那麼，倒數第二個參加的活動（如果有的話），就必須是「結束時間 ≤ s」的那些活動的其中一個。所以，對於任何一個可能的最後一個活動，其對應的子問題是那些把所有「結束時間 ≤ s」的活動留下來的另一個工作排程問題。

經過一陣推敲，不難發現「結束時間 ≤ x」的活動集合，會根據 x 越來越大，而使集合變得越來越大：而讓集合變得越來越大的順序，恰好就是將所有活動依照結束時間排序定義出來的順序。因此，我們可以首先針對 f[i] 進行排序，使得 f[0] ≤ f[1] ≤ ... ≤ f[n-1]。於是，對於每一個 i ，我們可以用二分搜尋法或雙指標法找出最大的 j 使得 f[j] ≤ s[i]，我們令 j = prev(i)。接著，我們可以正式地定義動態規劃函數 dp(i) 了！

方法一：加強式定義

我們定義 dp(i) 為「最後一個參與的活動恰好是第 i 個活動」這個情形下的最大成就點數總和。由於最後一個參與的活動恰好是 i，因此我們可以保證前一個活動必須是在 prev(i) 之前。所以可定義遞迴轉移：

最壞情形下 prev(i) = i-1，也就是說這個 max 在胡亂處理的情況下，計算整條 dp(0)...dp(n-1) 的情形需要 O(n^2) 時間。但這個 max 可以稍稍改良，大家可以稍微想一下，然後會發現變得跟方法二相同。

方法二：依循原問題

我們定義 dp(i) 為「從 0, 1, ..., i，這些活動中，挑選某些不重疊的活動參加，最大的成就點數總和」。與方法一不同的是，我們不限定最後一個活動是什麼。因此最佳解可能包含參加第 i 個活動、可能不參加第 i 個活動。根據這兩種情形，此時能夠參與到的前一個活動分別是 prev(i) 與 i-1。於是我們便能定義遞迴式：

是不是瞬間變得清爽多了呢？

備註：透過加強式的定義，通常會得到很直觀的動態規劃遞迴式。如果決定依循原問題定義，往往需要多思考一下才能確定其狀態轉移是否正確。但好處是，如果能夠得出精簡結論的話，通常比較好寫。

Exercise 17: Leetcode 309 - Best Time to Buy and Sell Stock with Cooldown

題目連結

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

題目敘述

給你連續 N 天每一天的股票價格，你每一天可以選擇買股票或是賣股票，但是賣完股票需要隔至少一天啥事都不能做，才能再買股票。同一時間至多只能持有一張股票。請問這 N 天跑完以後你的最大淨獲利是多少錢呢？（淨獲利指的是每一次賣出與買入的差價總和。這 N 天之內可以買賣多次，但仍必須滿足前述條件。）

解題思考

顯然第 k 天要幹麻，會是一個決定性的狀態。我們來考慮以下兩種思路吧：

• 定義 dp(k) = 若決定第 k 天要賣股票，則到第 k 天為止最大獲利為何。

因為已經決定要賣股票了，考慮買該張股票的時間點——假設是第 x 天好了，那麼再前一次賣股票的時間點只能是第 x-2 天以前了。這時間內當然挑獲利最高的解啊！所以我們有以下遞迴函數：

反正都要枚舉 x 了，因此這個 max 函數可以逐次更新，得到 O(n^2) 解。我們可以仿照工作排程的例子，換一套思考方式：

• 定義 dp(k) = 在第 k 天完成時，試問到第 k 天為止的最大獲利為何。

假定每一天股票價格都是正數的情形下，要達到最大獲利，在第 k 天我們並不會去買股票，也不會在第 k 天結束之後仍持有股票。因此，我們只可能在第 k 天脫手股票、或是啥事都不做。後者的情形顯然最大獲利是 dp(k-1)。至於前者的情形嘛，我們還是要寫一下哪天脫手股票：

你可能看了一下這遞迴式說，唉呀這還是 O(n^2) 啊，你到底在幹麻。但是式子變簡單了！變簡單以後就會出現決定性的觀察！比方說—— 第一點、A[k] 跟 max 函數一點關係都沒有。第二點、- A[x] + dp(x-2) 跟 k 一點關係都沒有，不同的 dp(k) 可以一起共用同一個值。於是乎，我們可以令 B[x] = - A[x] + dp(x-2)，然後把它拉出來分開算。

定義 dp2(k) = max{B[x]}，我們可以得知：

然後就莫名其妙得到一個線性時間的動態規劃了。為什麼？

有了這一層的推導過程以後，要解釋起來反而變得輕鬆多了：遞迴關係會這麼簡單，想必有其對應的意義！是的，其實很單純：dp(k) 定義的是在第 k 天結束之後「手上並無股票」而 dp2(k) 定義的則是在第 k 天結束之後「手上仍持有股票」的情形啊！這麼一來全部都解釋得通了！

如果你看到題目當下直接想到上面這兩行定義的話：恭喜你！你已經獲得動態規劃思維了～

參考程式碼 (Python3)

from collections import defaultdict

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = defaultdict(lambda: 0)
        dp2 = defaultdict(lambda: float("-inf"))
        for k in range(0, len(prices)):
            dp[k] = max(dp[k-1], prices[k] + dp2[k-1])
            dp2[k] = max(dp2[k-1], -prices[k] + dp[k-2])
        return dp[len(prices)-1]