[LeetCode] 198. House Robber

😎풀이

1. dp 배열을 nums.length의 길이로 생성한다.
2. 첫 집과 두번 째 집 중 도둑질 할 양이 큰 것으로 0번째와 1번째 배열을 채운다.
3. 세번째 집 부터 전 집 혹은 전전 집과 현재 집을 털이한 금액을 비교하여 최댓값으로 채운다.
4. dp배열의 마지막 요소를 통해 최대 금액을 반환한다.

function rob(nums: number[]): number {
    const n = nums.length
    const dp = Array(n)
    dp[0] = nums[0]
    dp[1] = 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]
};