Leetcode — 198. House Robber(中文)

問題連結: https://leetcode.com/problems/house-robber/

假設你是一個扒手, 而你有一個陣列紀錄著每個房子裡面放的錢, 唯一限制是你不能連續偷兩間房子, 不然警報器會啟動
求問在不驚動警報器的情況下, 最多可以偷多少錢

比如說input nums = [1,2,3,1]
那你最多可以偷4,
因為你不能連續偷兩間房子, 因此偷第一間跟第三間房子你能拿最多錢

想法:

典型的dynamic programming動態規劃問題
若你已經練習夠多問題, 你應該要能聯想到這題可以用動態規劃幫我們解決

而為何我們可以想到要用動態規劃的原因是因為在判斷我們在離開house i 時最多可以賺多少錢的時候, 我們必須考慮到我們在我們前面去過的幾個house時最多能賺多少錢, 也就是需要用到"遞迴呼叫方法來解決子問題",
而這種解題方法用動態規劃就最適合不過了, 我們用一個陣列來存我們之前解過的答案, 這樣就可以一直往前取值

dp[i] 代表我們從house 0開始每間都闖進, 在離開house i時, 總共最多可以偷多少錢.

我們可以快速地幫dp[i]得到下列公式 —

dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]) if i>=2

我們從house 0開始闖入每個家的時候, 都要在house i時, 做搶與不搶的決定:

1. 搶這間的話, 那我們最多可以拿到的錢就是 這間屋子的錢 加上 我們在離開 前前個屋子 的時候, 最多能累積的錢
2. 若不搶這間, 那我們最多可以拿到的錢 等於 我們在離開 前屋子 的時候最多能累積的錢

因為離開前屋子最多能累積的錢 有可能會包含"決定搶前屋子", 因此若我們決定搶"這間屋子"的話, 我們不能把前屋子的錢列入考量, 畢竟可能會因此觸動警鈴, 但我們可以放心地把 我們在離開前前屋子的時候,累積的錢考慮進去, 因為不管有沒有搶, 我們都不在乎! 💰

以下為 0ms的程式碼, 贏過99% —

public int rob(int[] nums) {
        int n = nums.length;
        if(n==0)
            return 0;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i = 1; i < n ; i++)
        {
            if(i<2)
                dp[i] = Math.max(nums[i],dp[i-1]);
            else
                dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[n-1];
    }

時間複雜度跟空間複雜度皆為 O(n).

我們也可以省去創建陣列的動作, 進而改善上述程式碼

因為我們發現上述程式碼, 其實我們只是一直在抓離開 前屋 及 前前屋 時候最多能累積的金錢, 因此我們只要多兩個變數來控制這兩個值即可-

1. prevTwo — 紀錄我們在離開前前屋 (house i-2) 時, 最多能偷多少
2. prevOne — 紀錄我們在離開前屋 (house i-1) 時, 最多能偷多少

也別忘記在每次離開house i 前, 更新上面兩個變數的值, 畢竟我們這輪被允許用的prevTwo和prevOne 就不會再是前前屋跟前屋的錢了

以下為 0ms 的程式碼, 贏過100% —

public int rob(int[] nums) {
        int n = nums.length;
        if(n==0)
            return 0;
        else if(n==1)
            return nums[0];
        
        int prevTwo = nums[0]; // house i-2
        int prevOne = nums[1]; // house i-1
        for(int i=2;i<n;i++)
        {
            int cur = Math.max(prevTwo+nums[i], prevOne);
            prevTwo = Math.max(prevTwo, prevOne);
            prevOne = Math.max(prevOne, cur);
        }
        return Math.max(prevOne,prevTwo);
    }

時間複雜度仍然是O(n), 但空間複雜度變為常數O(1)