目錄
🟨扒手I 回顧
在昨天的文章中留下了一個伏筆：能否換一個思路進行扒手問題的分治法，設計狀態，並且得到對應的轉移式？
題目是 Leetcode 198. House Robber
如果搶匪搶了目前的這間房子，那麼(從第一間到目前為止)最多可以搶多少錢？
提示：如果確定「搶了」目前的這間房子，那麼前一間被搶的，可能會是那些房子？
分析
分治法、設計狀態
我們可以將子問題(狀態)重新設計為：
money(i)代表：若已知搶匪搶了第i間房子，那麼(從第一間到目前為止)最多可以搶多少錢？
-
已知搶匪搶了第
i間房子，那麼他一定不能搶相鄰的第i-1間 -
搶匪可以搶第
i-2間，或者第i-3間，而且： -
他不能這兩間都不搶。因為若他只搶第
i-4間和第i間，那麼第i-2間也可以搶且不會觸發警報，若他不搶，就不可能是最佳答案。
狀態轉移式
對於money(i)狀態而言，搶匪必搶第i間，且必搶i-2或者i-3其中一間，因此對所有i>=3：
money(i) = nums[i] + max(money(i-2), money(i-3))
接者處理邊界條件：
money(0) = nums[0]
money(1) = nums[1]
money(2) = nums[0] + nums[2]
這個思路下，需要注意的是母問題和我們的子問題並不完全相同：
我們設計的子問題要求必定搶第
i間，但母問題並沒有強迫要搶最後一間，可以搶最後一間，也可以搶倒數第二間。(但不能兩間都不搶，因為這樣可以多搶最後一間，一定比較多錢)
因此，母問題所求的答案，其實等同於：
max(money(n), money(n-1))，其中n = len(nums)-1
實作
以Top-Down DP為例：
class Solution:
def rob(self, nums: List[int]) -> int:
# 假設：已知搶了第i間，則最多可搶多少錢
@cache
def money(i):
if i<=1: return nums[i]
if i==2: return nums[0]+nums[2]
return nums[i] + max(money(i-2), money(i-3))
return max(money(len(nums)-1) , money(len(nums)-2))
下面為同一題、使用昨天的思路的算法，可以比較其中的差異！
class Solution:
def rob(self, nums: List[int]) -> int:
# 第i間可以搶也可以不搶，則最多可搶多少錢
@cache
def money(i):
if i==0: return nums[0]
if i==1: return max(nums[:2])
return max(nums[i]+money(i-2), money(i-1))
return money(len(nums)-1)
透過本例我們可以發現，在一個動態規劃問題中，有時我們可能設計出不同的狀態與轉移式，但都能計算出相同的答案。
刷題時，當解開一題Medium或者Hard題，若時間充裕我也經常點開其他用戶的答案，參考比較別人的思路，有時也能找到自己沒想過的切入方向！
🟨扒手III
本題取自 Leetcode 337. House Robber III
題目
The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root.
Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night.
Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Example 1:
Input: root = [3,2,3,null,3,null,1]
Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:
Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
0 <= Node.val <= 10^4
相關概念
本題的村莊構成了一顆二元樹。本段僅就會用到的部分作簡單介紹！
如果對於樹不熟悉，因為樹本身也是很常出現的資料結構，建議除了動態規劃之外也學習一下樹的相關概念。
樹(Tree)
樹(Tree)是一種非封閉性的圖(Graph)，沒有環路(cycle)。
樹由一個根節點(root)與多個子節點(node)所構成。節點之間以代表父→子關係的線(edge)相鄰。
(除了root之外)每個node都有唯一的一個父節點(parent)
每個節點可以有數個子節點(child)。子節點的數量稱為degree。沒有子節點的節點又稱為葉節點(leaf)。
從根(root)往葉(leaf)走，形成一條分枝(branch)，每條分枝都可以看做一條Linked List。
例如我們電腦的目錄系統，每個檔案/資料夾都存放在一個資料夾中，就是一種樹的結構。
二元樹(Binary Tree)
如果某棵樹上，所有的節點都只能有至多兩個子節點，就稱之為二元樹(Binary Tree)
子節點有左右之分(left、right)。
樹的遍歷(Traversal)
學習樹(與所有圖論演算法)時，基本功就是能夠照特定的順序訪問一遍所有的節點。
我們先看看Leetcode上對於TreeNode類的定義：
Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
假設我們拿到一棵樹的root，要怎麼知道底下(child)有什麼東西呢？
就是取用root.left和root.right。至於root自己的值，則取用root.value。
那左邊的分支，底下又有什麼東西呢？就繼續對其查詢root.left.left和root.right.right……，直到我們抵達None，就代表該分枝已經走到尾端。
如果一個node的左右子節點都是None，代表這個node底下沒有任何節點，換言之，這個node就是leaf。
深度優先搜尋(DFS Depth First Search)
DFS是一個樹的遍歷演算法，可以描述如下：
- 從根開始
- 所有節點都先訪左分支，若有節點就繼續訪其左分支…。
- 若左分支訪問完畢(見下)，就繼續訪其右分枝。
- 若抵達
None，返回其父節點，這個分支訪問完畢。 - 若左右節點均訪問完畢，就回到其父節點，這個分支訪問完畢。
當然，順序也可以先訪右分枝，只是關鍵在於：先將某條分支走到底，再回頭走下一個分支。
用走迷宮來比喻，就是每個路口都挑一條走到底，先走到確定這條是死路，再往回找下一個分岔。
此處借用 Leetcode 94. Binary Tree Inorder Traversal來展示一下DFS：
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
def dfs(node):
if node is None: return # 這個分支沒有子節點了
dfs(node.left) # 訪左分支
ans.append(node.val)
dfs(node.right) # 訪右分枝
return # 左右都訪問完畢了
dfs(root) # 從root開始執行DFS
return ans
遍歷樹時，除了DFS，還有一個很常用的演算法是BFS(廣度優先搜尋，Broad First Search)，礙於本文篇幅不多贅述，有興趣的話可以參考延伸閱讀！
延伸閱讀
分析
分治法
規則是相鄰的房子(互相為parent-child的兩個node)不可以同時搶，因此，對於每一個節點會有兩種情況：
- 若搶了這個節點，則其子節點都不能搶
- 若沒搶這個節點，則其子節點可以搶，也可以不搶。
思考後可以發現，在我們設計狀態時，每個子問題都要回答兩個答案：
對於某個節點，包含底下所有的子節點，
- 如果搶了這個節點，則最多可以搶多少
- 如果這個節點不搶，則最多可以搶多少
設計狀態、找出轉移式與最小問題
狀態：定義money(node)用tuple回傳兩個解(ans0, ans1)分別為：
-
ans0表示未搶這個節點，的最大值 -
ans1表示搶了這個節點，的最大值
轉移式：
ans0：若沒搶這個節點，則底下兩個子節點都可以搶，也可以不搶。因此，答案應該加總：
-
node.left的
ans0、ans1中較大者 -
node.right的
ans0、ans1中較大者
ans1：若搶了這個節點，則底下的兩個子節點都不能搶。因此，答案應該加總：
node本身的錢node.valnode.left的ans0node.right的ans0
最小問題(邊界條件)：當抵達leaf節點(底下左右節點均為None)
不過，不用幫leaf節點設計不同的轉移式，只需要讓None節點回傳(0,0)即可
這樣做的好處是不用寫額外的判斷式判斷是否為leaf節點，廣義來說，可視為把None節點當作最小問題看待。
實作
Top-Down DP
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
def money(node): # 回傳(ans0, ans1)
# ans0: 不搶這個節點，則包含所有的子節點最多可以獲得多少
# ans1: 搶了這個節點，則包含所有的子節點最多可以獲得多少
# 邊界條件(最小子問題)
if node is None: return (0,0)
# 取得左child的兩個答案
moneyLeft = money(node.left)
# 取得右child的兩個答案
moneyRight = money(node.right)
return (
max(moneyLeft) + max(moneyRight), # ans0
node.val + moneyLeft[0] + moneyRight[0] # ans1
)
return max(money(root))
Bottom-Up DP
本題不適合使用Bottom-Up
因為本題的資料是樹狀結構，若要使用Bottom-Up，需要從每一個Leaf往Root計算。由於測資給的是Root，若要取得所有的Leaf，必需要先遍歷一次整棵樹。這個由根往葉遞迴的過程，其實和Top Down的計算順序一致，換言之本題採用Bottom-Up是多此一舉，並不適合。
這也是本系列第一次出現不適合使用Bottom-Up的題目。
若進一步分析，當資料結構屬於List、矩陣等較容易安排計算順序的型態時，適合使用Bottom-Up，而當資料結構包含圖等計算順序較為複雜，適合交給遞迴函式處理的型態時，則較適合使用Top-Down。
複雜度分析
時間複雜度
每個node被計算一次，因此時間複雜度 = O(n)，n為節點數量
空間複雜度
可以注意到本題並沒有使用到@cache，因為沒有節點被重複計算。
本題遞迴採用類似DFS的順序，因此遞迴深度最深為樹的高度。若測資為均勻分布，則空間複雜度 = 樹的高度 = O(log n)；在worst case，例如所有的測資均只有左child，則空間複雜度 = 樹的高度 = O(n)
🟨Delete and Earn
本題取自 Leetcode 740. Delete and Earn
題目
You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:
Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.
Return the maximum number of points you can earn by applying the above operation some number of times.
Example 1:
Input: nums = [3,4,2]
Output: 6
Explanation: You can perform the following operations:
- Delete 4 to earn 4 points. Consequently, 3 is also deleted. nums = [2].
- Delete 2 to earn 2 points. nums = [].
You earn a total of 6 points.
Example 2:
Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: You can perform the following operations:
- Delete a 3 to earn 3 points. All 2's and 4's are also deleted. nums = [3,3].
- Delete a 3 again to earn 3 points. nums = [3].
- Delete a 3 once more to earn 3 points. nums = [].
You earn a total of 9 points.
Constraints:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 104
分析
根據題目，我們可以選擇一個數n並得分，但是需要刪去所有值為n+1與n-1的數。
如果選擇一個n，則事實上我們將獲得每一個n的得分，(因為所有的n+1與n-1都在第一次選擇時就已經被刪光，所以後續繼續選擇剩餘的n將沒有任何損失)。
如果我們將這些數重新排列在數線上，可以發現：在數線上相鄰的數不可以同時獲得，這其實就是一個扒手問題！
實作
算法設計
- 建立數線：定義一個初值均為0的List
dp，並讓其長度等於max(nums)+1 - 遍歷一次
nums，將每個數排列在數線上：將每個值val加入dp中index==val的位置。 - 當作扒手問題來求解。
這邊用Bottom-Up DP來示範。
Bottom-Up DP
class Solution:
def deleteAndEarn(self, nums: List[int]) -> int:
# 資料預處理 (Counting Sort)
## 建立數線
dp = [0]*(max(nums)+1)
## 將nums中的數排列於數線上，並將相同的數加總
for n in nums:
dp[n] += n
# 解扒手問題
for i in range(2,len(dp)):
dp[i] = max(
dp[i-1], # 不取 i
dp[i] + dp[i-2] # 取 i
)
return dp[-1]
複雜度分析
時間複雜度
資料預處理時，遍歷一次nums需要O(n)，n為nums的長度
解扒手問題時，遍歷一次dp需要O(m)，m為max(nums)
時間複雜度 = O(n)+O(m) = O(n+m)
空間複雜度
我們建立了一個陣列來記錄數線上的位置，因此空間複雜度 = O(m)，m為max(nums)
複雜度優化
本題由於測資的值範圍較小，可以使用類似Counting Sort的方式來建立dp陣列作為數線，並且把原本的題目「當作」數線上的扒手問題求解。但倘若測資的值範圍更大，則將浪費更多的時間與空間。
各位讀者也可以延伸思考看看：若本題的測資nums的長度不大，但nums[i]的值範圍很大時，應該如何調整動態規劃的設計，來讓時間、空間複雜度不再依賴於max(nums)。
結語
在今天的第一題，首次遇到了動態規劃結合其他資料結構的題型。對於DP結合圖論演算法問題，子問題可能是求「到某個節點為止」的答案，也可能是求某個時間點時、整張圖的狀態(圖隨時間而變的題型)。若初見題目覺得難以規劃，可以試著畫出對應的圖形來思考應該如何分治題目成較小的問題。
在第二題，我們學習到，某些問題在經過簡單的轉化之後，可以「視為」動態規劃的模板題 來求解。這種轉換視角的做法在演算法問題中也很常見，在學習刷題時，先多練習常見演算法的模板問題，能有助於我們舉一反三。
以上為Day5的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！
本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。
DP之旅的第一個模板題形－費波那契數列就暫時到本文告一個段落，明天起我們會探索一個類似的題型：矩陣。