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

Intuition

• 연속한 집을 선택하지 않을 수 있음
• i >= 3 일 때, i번쨰 집은 i-2나 i-3번째 집 중에서 올 때 최댓값일 수 있다. i-2나 i-3번까지의 집을 턴 돈 중에서 더 큰 값을 가진 곳에서 i번째 집으로 올 때 최댓값이 된다.
  • i-4에서 i로 바로 올 수도 있으나 i-4 다음에 i-2를 거쳐서 오는게 i번째까지의 집을 터는데 더 많은 돈을 털 수 있다. 그러니 i-2나 i-3번째 집에서 오는 것만 후보로 생각한다.
  • i-3번째 집이 후보가 될 수 있는 이유는, [4, 1, 1, 3]이 예시가 된다. 첫 번째 집과 네 번째 집을 터는 것이 최댓값이다.

Approach

• N은 nums의 길이, sum은 i번째 집을 터는데 최댓값
• Base Case:
  • N이 1일 때, nums[0]
  • N이 2일 때, nums[0]과 nums[1] 중 최댓값
  • N이 3일 때, nums[0] + nums[2]와 nums[1] 중 최댓값

• sum[0] = nums[0], sum[1] = nums[1], sum[2] = nums[0]+nums[2]
• i가 [3, N)인 영역에서 다음을 반복
  • sum[i]는 nums[i] + Math.max(sum[i-2], sum[i-3])
• sum의 마지막과 마지막-1 번째 중 최댓값

Complexity

• Time complexity: O(N)

• Space complexity: O(N)

Code

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const N = nums.length;
    if(N === 1){
        return nums[0];
    }
    if(N===2){
        return Math.max(nums[0], nums[1]);
    }
    if(N===3){
        return Math.max(nums[0]+nums[2], nums[1]);
    }
    const sum = new Array(N);
    sum[0] = nums[0];
    sum[1] = nums[1];
    sum[2] = nums[0]+nums[2];
    for(let i = 3; i < N; i++){
        sum[i] = nums[i] + Math.max(sum[i-2], sum[i-3]);
    }
    return Math.max(sum.pop(), sum.pop());
};