198. House Robber

---

My Solution

Solution 1: Brute force (TLE)

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    int rob(vector<int>& nums) {
        return dp(nums, nums.size() - 1);
    }
    
private:
    int dp(vector<int>& nums, int i) {
        if (i == 0) {
            return nums[0];
        }
        
        if (i == 1) {
            return max(nums[0], nums[1]);
        }

        return max(dp(nums, i - 2) + nums[i], dp(nums, i - 1));
    }
};

Time Complexity

$O(2^n)$

$n$ is the length of nums.

Space Complexity

$O(n)$

Solution 2: Top-down DP

The Key Idea for Solving This Coding Question

C++ Code 1

class Solution {
public:
    int rob(vector<int> &nums) {
        unordered_map<int, int> memo;
        
        memo[0] = nums[0];
        if (nums.size() == 1) {
            return memo[0];
        }
        
        memo[1] = max(nums[0], nums[1]);
        if (nums.size() == 2) {
            return memo[1];
        }
        
        return dp(nums, memo, nums.size() - 1);
    }
    
private:
    int dp(vector<int> &nums, unordered_map<int, int> &memo, int i) {
        auto iter = memo.find(i);
        if (iter != memo.end()) {
            return iter->second;
        }
        
        memo[i] = max(dp(nums, memo, i - 2) + nums[i], dp(nums, memo, i - 1));
        return memo[i];
    }
};

C++ Code 1

class Solution {
public:
    int rob(vector<int> &nums) {
        vector<int> memo(nums.size(), -1);
        
        memo[0] = nums[0];
        if (nums.size() == 1) {
            return memo[0];
        }
        
        memo[1] = max(nums[0], nums[1]);
        if (nums.size() == 2) {
            return memo[1];
        }
        
        return dp(nums, memo, nums.size() - 1);
    }
    
private:
    int dp(vector<int> &nums, vector<int> &memo, int i) {
        if (memo[i] >= 0) {
            return memo[i];
        }
        
        memo[i] = max(dp(nums, memo, i - 2) + nums[i], dp(nums, memo, i - 1));
        return memo[i];
    }
};

Time Complexity

$O(n)$

$n$ is the length of nums.

Space Complexity

$O(n)$

Solution 3: Buttom-up DP

The Key Idea for Solving This Coding Question

C++ Code

class Solution {
public:
    int rob(vector<int> &nums) {
        vector<int> dp(nums.size(), -1);
        
        dp[0] = nums[0];
        if (nums.size() == 1) {
            return dp[0];
        }
        
        dp[1] = max(nums[0], nums[1]);
        if (nums.size() == 2) {
            return dp[1];
        }
        
        for (int i = 2; i < nums.size(); ++i) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        
        return dp.back();
    }
};

Time Complexity

$O(n)$

$n$ is the length of nums.

Space Complexity

$O(n)$

Miscellaneous