(Leet Code JS)House Robber II

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

House Robber II - LeetCode

 

DP 알고리즘.

nums의 length만큼 DP 배열을 선언하여 0으로 초기화 한다.

DP 배열은 총 2개를 선언하는데,

이는 0번째 집을 털었을 때의 경우 = dp1,

0번째 집을 털지 않았을 경우 = dp2 로 계산하기 위함이다.

(0번째 집을 털었을 경우는 마지막 집을 털수 없기 때문)

 

for문은 2 ~ length 만큼 반복.

 

dp2는 전형적인 점화식으로 진행한다.

dp1은 조건을 걸어 i가 length - 1인 경우만 특수하게 처리하고, 나머지는 dp2의 점화식과 동일하게 적용하면 된다.

즉, dp1의 특수 처리는 0번째 집을 털었기 때문에 마지막 집을 털수 없는 경우로, 마지막 집 이전까지의 결과를 그대로 적용해야 한다.

 

리턴값은 두 DP 배열의 마지막 값 중 더 큰 값을 리턴한다.

 

const rob = (nums) => {
    const length = nums.length;
    const dp1 = Array(length).fill(0);
    const dp2 = Array(length).fill(0);
    
    dp1[0] = nums[0];
    dp1[1] = nums[0];
    dp2[1] = nums[1];
    
    for(let i = 2; i < length; i++){
        if(i !== length - 1){
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        } else{
            dp1[i] = dp1[i - 1];
        }
        
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
    }
    
    return Math.max(dp1[length - 1], dp2[length - 1]);
};