LeetCode 198 - House Robber (Easy)

문제

LeetCode - 198번

풀이 과정

도둑질을 통해 얻을 수 있는 최대 수익을 구하는 동적 계획법 문제입니다.

만약 dp(house) = house 에서부터 마지막 집까지 도둑질을 통해 얻을 수 있는 최대 수익 이라고 한다면,
다음과 같은 점화식을 세울 수 있습니다.

dp(house) = max(dp(house+1), dp(house + 2) + cost[house])

여기서 두 가지로 나누어지는 이유는 현재 house 위치에서 도둑질을 하는 것과 안하는 것 이렇게
두 가지 경우가 있기 때문입니다.

코드

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const memo = new Array(nums.length).fill(-1);

  function dp(i) {
    if (i >= nums.length) return 0;
    if (i === nums.length - 1) return nums[i];

    if (memo[i] !== -1) return memo[i];

    memo[i] = Math.max(dp(i + 1), dp(i + 2) + nums[i]);
    return memo[i];
  }

  return dp(0);
};