(Leet Code JS)House Robber

https://leetcode.com/problems/house-robber/

House Robber - LeetCode

 

DP 이용.

nums.length만큼 dp 배열을 선언하여 0으로 초기화.

 

dp[0] = nums[0]으로 저장하고 for문으로 1 ~ length만큼 반복한다.

점화식으로는 dp[i] = Math.max(nums[i] + (dp[i - 2] || 0), dp[i - 1])을 구할 수 있다.

dp[i - 2] || 0 은 i = 1부터 시작하기 때문에 i - 2가 배열의 범위를 벗어나서 undefined가 나온다.

이를 방지하기 위해 undfeind가 나오면 0을 더해준다.

 

리턴값은 dp[length - 1]을 한다.

var rob = function(nums) {
    const length = nums.length;
    const dp = Array(length).fill(0);
    
    dp[0] = nums[0];
    
    for(let i = 1; i < length; i++){
        dp[i] = Math.max(nums[i] + (dp[i - 2] || 0), dp[i - 1]);
    }
    
    return dp[length - 1];
};