House Robber

[kokocan12]

Problem

When an array is given, each element means amount of cash stored in a house, find maximum cash sum you can rob.
Adjacent houses has a connection, so you can not rob houses adjacent.

example
Input: nums = [1,2,3,1]
Output: 4

Approach

Using DP, calculate maximum cash sum until index i.
dp[i] means the maximum sum that contains nums[i].

/**
 * [1,2,3,1,5]
 * 
 * Using DP
 * The max sum until index 0 is..
 * nums[0] itself.
 * The max sum until index 1 is..
 * Max(dp[0], nums[1])
 * The max sum until index 2 is..
 * Max(dp[0]+nums[2], dp[1])
 * The max sum unitl index 3 is..
 * Max(dp[2], dp[0]+nums[3], dp[1]+nums[3])
 * The max sum until index 4 is..
 * Max(dp[1]+nums[4], dp[2]+nums[4], dp[3])
 */
const rob = function(nums) {
    let max = 0;
    const dp = {};
    dp[-1] = 0;
    dp[-2] = 0;
    dp[-3] = 0;
    
    for(let i=0; i<nums.length; i++) {
        const num = nums[i];
        
        dp[i] = Math.max(num+dp[i-2], num+dp[i-3]);
        
        max = Math.max(dp[i], dp[i-1]);
    }
    
    return max;
};