[75 LeetCode] 40 - House Robber

[75 LeetCode]는 코딩테스트 연습을 위해 한 페이스북 개발자가 추천하는 75가지 알고리즘 문제를 풀어보는 시리즈이다.

블라인드 원문:
https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU

문제 링크: https://leetcode.com/problems/house-robber/description/

House Robber - LeetCode

 

대표적인 DP문제다.

i + 1 번째 까지 선택 시 최대 값은 MAX((i - 1번째까지 최대 값) + (i + 1번째 값), (i번째까지 최대값))이 된다.
1) i + 1번째 값을 선택하려면 i번째까지의 최대값은 사용할 수 없기 때문에 i - 1번째까지의 최대값과 더해야한다.
2) 선택하지 않는경우는 i번째까지 최대값이다.
두 경우 중 큰 값이 i + 1번째까지 선택이 가능할 때의 최대값이된다.

var rob = function(nums) {
    nums.push(0);
    const dp = [0, nums[0]];

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

더 빠른 풀이들은 DP를 두지 않고 변수에 담아서 사용한다.
생각해보면 dp의 값을 계속 사용하지 않고 다음, 다다음 순회에서만 사용하기 때문에 그게 훨씬 효율적일것이다.