題目連結: 198. House Robber

題目描述:如果兩間直接相鄰的房屋在同一天晚上被偷，就會自動觸發警報系統。
給定一個代表每個房屋存放金額的非負整數陣列 nums，請計算你在不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高總金額。
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Python

解題思路:
當我們走到第 i 間房子的時候，若選擇不偷，計算偷前 i-1 間房子的最高金額;選擇偷的話，總金額等於「偷到第 i-2 間房子為止的最高金額」加上「當前這間房子 nums[i-1] 的錢」。

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp0 = 0
        dp1 = 0
        for i in nums:
            curr = max(dp1, i + dp0)
            dp0 = dp1
            dp1 = curr
        return dp1

演算法分析:

• dp0: 代表偷到「前兩間」房子的最高金額 (相當於 dp[i-2])、dp1: 代表偷到「前一間」房子的最高金額 (相當于 dp[i-1])。
• curr = max(dp1, i + dp0)在面對當前這間房子 i 時，我們做出一個選擇：
  1.不偷：如果我們不偷當前這間房子 i，那麼我們能得到的最高金額，就等於偷到前一間房子為止的最高金額，也就是 dp1。
  2.偷：如果我們決定偷當前這間房子 i，根據規則我們就不能偷前一間。所以我們的總金額等於當前房子的錢 i 加上偷到前兩間房子為止的最高金額 dp0，也就是 i + dp0。
• 最後是做空間優化。在準備去下一間房子之前，我們需要更新我們的「記憶」，dp0 = dp1：原本「前一間」的最高金額 dp1，在下一輪就變成了「前兩間」的最高金額，dp1 = curr：我們剛剛算出的「當前」最高金額 curr，在下一輪就變成了「前一間」的最高金額。

複雜度分析:

• 時間複雜度為 O(n)(演算法的核心是一個 for 迴圈，它遍歷了 nums 陣列一次。)。
• 空間複雜度： O(1)(只使用了 dp0, dp1, curr 等幾個固定數量的變數。)。

注意迴圈內dp0、dp1值的替換順序不可變。
有問題可以底下留言!
下回見!!