LeetCode Digest
3 分鐘 閱讀文 (大約 384 個字)

House Robber

題目
思路

  1. 可以把得出答案的過程拆解為最小可重複步驟，用遞迴來解
  2. Recursive case: 假設 index 為 i，由 index 0 搶到 i 可得的最大收穫為 inner_rob(i)。在位置 i, 可選擇搶或不搶：
    1. 不搶：最大收穫跟前一個點一樣，為 inner_rob(i - 1)
    2. 搶：代表前一個點一定是不搶，所以最大收穫為這個點的 money nums[i] 再加上前前個點的最大收穫 inner_rob(i - 2)
    • 所以 inner_rob(i) 為以上兩種情況取較大的那個
  3. Base case (終止條件)：i < 0
  4. 因為這個遞迴解的時間複雜度最差為 O(2^n)，必須降低，我們可以把計算過的 inner_rob(i) 使用 @cache 將 function 回傳 cache 起來，避免同樣的 inner_rob(i) 重複計算

Python3 solution:

1
2
3
4
5
6
7
8
def rob(self, nums: List[int]) -> int:
    @cache
    def inner_rob(i):
        """@return 由 index 0 搶到 i 可得的最大收穫"""
        if i < 0:
            return 0
        return max(inner_rob(i - 1), nums[i] + inner_rob(i - 2))
    return inner_rob(len(nums) - 1)
  • 時間複雜度：O(n)
    • 因為有記憶，每個點只會計算一次，共有 n 個點
  • 空間複雜度：O(n)
    • cache 需要的空間為 n，遞迴的最大深度也是 n

以上，如果不用 @cache 的話：

1
2
3
4
5
6
7
8
9
10
def rob(self, nums: List[int]) -> int:
    memo = [None] * len(nums)
    def inner_rob(i):
        if i < 0:
            return 0
        if memo[i] is not None:
            return memo[i]
        memo[i] = max(inner_rob(i - 1), nums[i] + inner_rob(i - 2))
        return memo[i]
    return inner_rob(len(nums) - 1)
# ,
遞迴的時間複雜度算法
Unique Paths

評論

分類

標籤雲

android array authentication binary search binary search tree binary tree bit manipulation breadth-first search database depth-first search distributed system django docker dokku dynamic programming graph greedy hash table heap heroku java jwt linked list matrix mysql paas package management pipenv postgresql python recursion shortest path simulation sliding window sorting stack string tree two pointers

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3

最新文章

彙整

標籤

android 2
array 5
authentication 1
binary search 1
binary search tree 1
binary tree 6
bit manipulation 2
breadth-first search 5
database 2
depth-first search 9
distributed system 1
django 1
docker 3
dokku 1
dynamic programming 4
graph 2
greedy 1
hash table 6
heap 1
heroku 1
java 1
jwt 1
linked list 5
matrix 1
mysql 1
paas 1
package management 1
pipenv 1
postgresql 1
python 9
recursion 11
shortest path 1
simulation 1
sliding window 1
sorting 1
stack 2
string 4
tree 7
two pointers 3
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×