[LeetCode] 198. House Robber, Medium

1. 문제

• 집에 가지고 있는 금액 배열인 nums가 주어진다. 한 집을 털면 양 옆 집은 경찰이 출동하기 때문에 털 수 없다고 할 때, 최대로 털 수 있는 금액을 반환하라.

2. 해결

function rob(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];
    if (n === 2) return Math.max(nums[0], nums[1]);

    const dp = [nums[0], Math.max(nums[0], nums[1])];

    
    for(let i = 2; i< n; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]); 
    }

    
    return dp[n-1]
};

• 첫 풀이 때 3번째 부터 점화식을 세워서 풀긴 했는데, 그렇게 할 필요가 없었다.
• 우선 0~2번 인덱스 까지는 예외처리를 해주고, 0번은 그대로, 1번은 0과 1중 가장 큰 값을 넣는다. (해당 집을 털었을 때의 최대 비용이므로.)
• 3번 인덱스는 비교 대상이 1. 직전 집의 최대 값, 2. 2개 전의 집을 턴 최대값 + 현재 집의 코스트를 비교하여 저장한다.
• 마지막 집을 털었을 때 가질 수 있는 최대 비용이 마지막 인덱스에 담긴다.