LeetCode 198 House Robber

Last updated on an hour ago

題目連結

❗️ 題意

給定一個陣列 $nums$，請你從裡面竟可能的選擇總和最大的數值，並且不能夠選擇相連的數字，最後請輸出能夠從此陣列中拿到的最大值為何。

  • Input: $[1,2,3,1]$

  • Output: $4$

    • $nums[0] + nums[2] = 4$

  • Input: $[2,7,9,3,1]$

  • Output: $12$

    • $nums[0] + nums[2] + nums[4] = 12$

  • Constraints:

    • $1 \leq nums.length \leq 100$
    • $0 \leq nums[i] \leq 400$

✔️ 題解

首先，我們可能會很直覺的想到，是否我們只需要選擇index全部為奇數或全部為偶數加起來即可，但很明顯此方法是錯的，例如 $[10, 1, 1, 10]$ ，若只選奇數或只選偶數最大皆只有 $11$ ，但若我們拿 $nums[0]$ 與 $nums[3]$ 便可以獲得 $20$ 。
因此我們可以透過類似於 Climing Stairs的方法來思考此題，假設我們要選擇房子 $i$ ，則必定保證房子 $i - 2$ 房子 $i - 3$ 一定有一個被選到，因為全部的數值皆為正數，就算有那種需要橫跨數個來選的(例如橫跨四個以上，中間的 $i - 2$ 與 $i - 3$ 一定有一個也可以被選)。因此此問題就能簡化成以下式子： $dp[i] = nums[i] + max(dp[i - 2], dp[i - 3])$
而在實作上，不管Top-Down或Button-Up的作法皆可以成功解決此問題。

💻 程式碼

  • Top-Down(with Memoization)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    // 2 ms, AC
    class Solution {
    public:
        vector<int> dp;
        int n = 0;
        int solve(int h, vector<int>& nums){
            if(h < 0){
                return 0;
            }
            else if(h < 2){
                return dp[h] = nums[h];
            }
            else if(dp[h] != -1){
                return dp[h];
            }
            return dp[h] = nums[h] + max(solve(h - 2, nums), solve(h - 3, nums));
        }
        int rob(vector<int>& nums) {
            if(nums.size() == 1){
                return nums[0];
            }
            n = nums.size();
            dp.resize(n);
            fill(dp.begin(), dp.end(), -1);
            return max(solve(n - 1, nums), solve(n - 2, nums));
        }
    };

  • Button-Up

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    // 0ms, AC
    class Solution {
    public:
        int rob(vector<int>& nums) {
            if(nums.size() == 1){
                return nums[0];
            }
            int n = nums.size();
            for(int i = 2; i < n; i++){
                if(i == 2){
                    nums[i] += nums[i - 2];
                }
                else{
                    nums[i] += max(nums[i - 2], nums[i - 3]);   
                }
            }
            return max(nums[n - 1], nums[n - 2]);
        }
    };

    Runtime: 0 ms, faster than 100% of C++ online submissions

類似問題： 213 House Robber II

  • 此題與 House Robber唯一的差別為其房子排序為一個環，代表第一個房子與最後一個房子也是相連的，而我們同樣可以透過類似的概念來完成此問題。

  • 在實際上，我們可以分為兩個Cases，Case1是是不使用第一個房子，但使用最後一間(實作上直接將第一個房子設為0即可)，Case2則相反，使用第一個房子而不使用最後一間，並分別對兩個Case用上面的方法求解即可

  • Button-Up

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    // 0ms, AC
    class Solution {
    public:
        int rob(vector<int>& nums) {
            if(nums.size() == 1){
                return nums[0];
            }
            if(nums.size() == 2){
                return max(nums[0], nums[1]);
            }
            int n = nums.size();
            vector<int> v1 = nums;
            v1[0] = 0;
            vector<int> v2 = nums;
            for(int i = 2; i < n; i++){
                if(i == 2){
                    v1[i] += v1[i - 2];
                    v2[i] += v2[i - 2];
                }
                else{
                    v1[i] += max(v1[i - 2], v1[i - 3]);
                    v2[i] += max(v2[i - 2], v2[i - 3]);   
                }
            }
            return max(max(v1[n - 1], v1[n - 2]), max(v2[n - 2], v2[n - 3]));
        }
    };

    Runtime: 0 ms, faster than 100% of C++ online submissions

🧠 心得

這兩題真的蠻像的，第二題甚至只需要複製前一提的程式再稍微改一下即可！