---
tags: leetcode
---

# [198. House Robber](https://leetcode.com/problems/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
<!--
# Test Cases

[1,2,3,1]

[2,7,9,3,1]

[0]

[213,59,76,87,209,98,94,175,249,123,109,233,199,162,51,92,146,154,146,118,183]

[114,117,207,117,235,82,90,67,143,146,53,108,200,91,80,223,58,170,110,236,81,90,222,160,165,195,187,199,114,235,197,187,69,129,64,214,228,78,188,67,205,94,205,169,241,202,144,240]

[1,7,9]

[1,3,2,3,2,4,6,3]

-->