198. House Robber - cocoder39/coco39_LC GitHub Wiki

198. House Robber

2020 Notes: A good post about how to approach DP problem.

a robber has 2 options at each index:

  • if rob i, then he cannot rob i-i, so the cumulative scores is cumulative_scores_till_index_i-2 + nums[i]
  • if not rob i, then the cumulative scores at index i is equal to the cumulative scores at index i-1

dp[i]: the cumulative scores he can get from [0 ... i]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n <= 2:
            return max(nums)
        
        dp = [0] * n
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        
        res = max(dp[0], dp[1])
        for i in range(2, n):
            dp[i] = max(dp[i-2] + nums[i], dp[i-1])
            res = max(res, dp[i])
        
        return res

========================================================================================================================

int rob(vector<int>& nums) {
        int sz = nums.size();
        if (sz == 0) {
            return 0;
        }
        
        vector<int> rob(sz + 1); //rob[i] is max can get if rob nums[i]
        vector<int> unrob(sz + 1); //unrob[i] is max can get if not rob nums[i]
        
        for (int i = 1; i <= sz; i++) {
            rob[i] = unrob[i - 1] + nums[i - 1];
            unrob[i] = max(rob[i - 1], unrob[i - 1]);
        }
        return max(rob[sz], unrob[sz]);
    }

int rob(vector<int>& nums) {
        int sz = nums.size();
        if (sz == 0) {
            return 0;
        }
    
        int rob = 0, unrob = 0;
        for (int i = 1; i <= sz; i++) {
            int prev_rob = rob, prev_unrob = unrob;
            
            rob = prev_unrob + nums[i - 1];
            unrob = max(prev_rob, prev_unrob);
        }
        return max(rob, unrob);
    }
⚠️ **GitHub.com Fallback** ⚠️