198. House Robber

📝 Problem Details

• Title: 198. House Robber
• Link: https://leetcode.com/problems/house-robber/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input integer array nums representing the amount of money of each house

💭What Were My Initial Thoughts?

1. Subproblem
    - At each house i, decide to rob it or skip it
    - If robbing, take nums[i] and add the best solution from i-2
    - If skipping, take the value from i-1
    - Goal: Maximize total money robbed

2. Top-Down vs. Bottom-Up
    - Bottom-up is better to avoid recursion overhead
    - Top-down with memoization works but is unnecessary

3. Define DP State
    - dp[i] stores the max money robbed up to house[i]

4. Transition Formula
    - dp[i] = max(dp[i-1], dp[i-2] + nums[i])

5. Optimize Space
- Only dp[i-1] and dp[i-2] are needed at any time
- Use two variables instead of an array for O(1) space
- For learning, a full DP table (`O(n)` space) is fine

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n) but can be optimized to O(1)

💻 Implementation of Solution

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