213. House Robber II

發表於 | 分類於

problem

solution

一個只搶[1,n-1]，另一個只搶[0,n-2]，再取最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int rob(vector<int>& nums, int l, int r){
        if(r==l) return nums[l];
        int dp0 = nums[l], dp1 = max(nums[l],nums[l+1]);
        int ret = dp1;
        for(int i=l+2;i<=r;++i){
            ret = max(dp0+nums[i], dp1 );
            dp0 = dp1;
            dp1 = ret;
        }
        return ret;
    }
    int rob(vector<int>& nums) {
        // option 1 因為只會發生兩種情況。
        // 從第一家開始搶，就不能搶第 n-1
        // 從第二家開始搶，就可以一直搶下去
        int n = nums.size();
        if(n==1) return nums[0];
        int l = 0, r = n-1;
        return max(rob(nums, l+1, r), rob(nums, l,r-1));
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)