合縱連橫: 從區間DP理解House Robbery系列題 背後的本質
這篇文章，會帶著大家複習以前學過的區間DP框架，
並且以區間DP的概念為核心，
貫穿一些相關聯的題目，透過框架複現來幫助讀者理解這個實用的演算法框架。
基本的區間DP框架(限制條件: 相鄰的兩項不允許同時選擇)
在House Robbery這題中，我們學會了一種基本的區間DP框架。
也就是在相鄰兩個元素不允許同時選擇的情況下，進行獲利最大化的最佳化。
對於第i個元素來說，其實總共只有兩種可能
第一種: 挑選第i個元素 (這回合獲利+nums[i])
再配合題意的限制，一旦選擇了第i個元素，下一個相鄰的第i-1個元素就必須放棄。
獲利最大化的情況變成DP[i-2] + nums[i]
第二種: 放棄第i個元素 (這回合沒有獲利 +0)
再配合題意的限制，這回合放棄第i個元素，下一回合的第i-1個元素可以納入考慮的區間。
獲利最大化的情況變成DP[i-1] + 0
那麼獲利最大化，自然是
max( 第一種情況, 第二種情況)
= max( 挑選第i個元素, 放棄第i個元素 )
= max( take, skip)
= max( DP[i-2] + nums[i], DP[i-1] + 0 )
寫成虛擬碼或演算法，就成為下面這個樣子
def consider( i ):
# look-up table
if i in dp:
return dp[i]
# base case
if i == 0:
dp[0] = nums[0]
return dp[0]
# base case
if i == 1:
dp[1] = max(nums[0], nums[1])
return dp[1]
# general case
take = nums[i] + consider(i-2)
skip = 0 + consider(i-1)
dp[i] = max( take, skip )
return dp[i]
接下來，我們會用這個上面這種結構，貫穿一些同類型，有關聯的題目
(請讀者、或觀眾留意上面的這種DP結構，之後的解說會反覆出現)
House Robbery
幾本上，是使用同樣的結構，
相鄰兩個元素不允許同時選擇的情況下，進行獲利最大化的最佳化。
class Solution:
def rob(self, nums: List[int]) -> int:
# DP table
# key: index i
# value: max rob value consider from 0 to i, inclusively
dp = {}
def consider( i ):
# look-up table
if i in dp:
return dp[i]
# base case
if i == 0:
dp[0] = nums[0]
return dp[0]
# base case
if i == 1:
dp[1] = max(nums[0], nums[1])
return dp[1]
# general case
take = nums[i] + consider(i-2)
skip = 0 + consider(i-1)
dp[i] = max( take, skip )
return dp[i]
# ----------------------------------------
last_house = len(nums)-1
return consider(last_house)
那還有沒有別的題目用到類似的結構呢?
其實有喔!
Delete and Earn
題目要求相鄰的整數不能一起取，
那其實換個等價的敘述來講，
就是整數i 和 整數i-1不能同時選擇。
透過演算法的化簡技巧，就被我們映射到已經會解的House Robbery DP 框架
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
# score is the storage to collect all the copies of distinct integers in input array
score = [0] * (max(nums)+1)
# score[i] save all the copies of corresponding number in input array
for number in nums:
score[number]+= number
# Reduce to the House Robbery Problem I
# Leetcode #198: https://leetcode.com/problems/house-robber/
size = len(score)
if size <= 2:
return max(score)
max_points = [0 for _ in range(size)]
max_points[0] = score[0]
max_points[1] = max(score[0], score[1])
for i in range(2, size):
take_integer_i = max_points[i-2] + score[i]
not_to_take_integer_i = max_points[i-1] + 0
max_points[i] = max( take_integer_i, not_to_take_integer_i)
return max_points[-1]
好，接著再進階一點的類似題。
假如頭尾也被視為相鄰(就好像環狀佇列的那種形狀)，該怎麼計算?
其實也是類似的。
假如頭尾也被視為相鄰，那麼也只有兩種情況:
第一種情況:
選了第一棟，那麼最後一棟必須放棄(因為題目額外多加了限制條件)。
第二種情況:
選了最後一棟，那麼第一棟必須放棄(因為題目額外多加了限制條件)。
那麼獲利最大化，自然是
max( 第一種情況, 第二種情況)
= max( solve(nums[:-1]), solve(nums[1:]) )
class Solution:
def rob(self, nums: List[int]) -> int:
def solve( arr ):
dp = {}
def consider( i ):
# look-up table
if i in dp:
return dp[i]
# base case
if i == 0:
dp[0] = arr[0]
return dp[0]
# base case
if i == 1:
dp[1] = max(arr[0], arr[1])
return dp[1]
# general case
take = arr[i] + consider(i-2)
skip = 0 + consider(i-1)
dp[i] = max( take, skip )
return dp[i]
# =======================================
return consider( i = len(arr)-1 )
# ----------------------------------------------------
if len(nums) == 1:
return nums[0]
return max( solve(nums[:-1]), solve(nums[1:]) )
House Robber III
接著，再更上一層樓，假如在樹狀結構上，也可以嗎?
這題的題意和限制條件也非常相似。
改成在二元樹上挑選節點，
限制條件改成 上下相鄰的兩層，不能同時挑選。
那其實也只有兩種情況
第一種情況:
選了第i層，那麼第i+1層必須放棄(因為題目的限制條件)。
第二種情況:
放棄了第i層，那麼第i+1棟可以納入考慮(因為題目的限制條件)。
那麼獲利最大化，自然是
max( 第一種情況, 第二種情況)
= max( 選第i層, 不選第i層 )
class Solution:
def rob(self, root: TreeNode) -> int:
def consider(node) -> (int, int):
if not node:
# take, not to take
return (0, 0)
left = consider(node.left)
right = consider(node.right)
# pick current level , discard current level
return (node.val + left[1] + right[1], max(left) + max(right) )
# ---------------------------------
return max( consider(node=root) )
結語
好，今天一口氣介紹了最精華的部分，
通用的區間DP框架 + 相鄰的兩項不能同時選擇的限制條件，
還有相關的衍伸變化題與演算法化簡流程，
希望能幫助讀者、觀眾徹底理解它的原理，
並且能夠舉一反三，洞察其背後的本質和了解相關的應用領域！
感謝收看囉! 我們下篇文章再見~
