198. House Robber

發表於 | 分類於

problem

solution

維護一個dp，max(dp[i-1], dp[i-2]+nums[i])

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

            int n = nums.size();
            vector<int> dp(n,0);
            if(n==1) return nums[0];
            int dp0 = nums[0], dp1 = max(nums[0], nums[1]);
            int ret = dp1;
            for(int i=2;i<n;++i){
                ret = max(dp0 + nums[i], dp1);
                dp0 = dp1;
                dp1 = ret;
            }
            return ret;
        }
    };

    analysis

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