House Robber

198. House Robber

문제

거리에 집들이 나란히 있다. 문제는 인접한 집을 연속해서 털면 경보시스템이 작동하여 자동으로 구속된다. 첫번째 집에서 마지막 집까지(경찰에 알리지 않고) 훔칠 수 있는 최대 금액을 구하는 문제이다. 가장 먼저 생각나는 것은 탐욕법였는데, dp 카테고리에 있어서 둘 다 풀어보기로 했다.

테스트 케이스

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

DP 풀이

1. (입력값은 1부터 주어지며) 두 집에 해당하는(nums[0], nums[1])이라면 바로 반환한다.
2. 집을 털었을 때 금액을 누적하는 dp 배열을 생성한다.
3. 첫번째, 두번째 집은 dp 배열에 초기화한다.
4. nums를 반복하면서 현재 nums[i] + nums[i-2]와 nums[i-1]의 값 중 큰 값을 nums[i]에 저장한다.
5. dp 의 가장 마지막 값을 반환한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  if (nums.length === 1) return nums[0]
  if (nums.length === 2) return Math.max(nums[0], nums[1])

  const dp = new Array(nums.length)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])

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

  return dp[nums.length - 1]
};

greedy 탐욕법 풀이

dp와는 다르게 배열을 저장하는 것이 아니라, nums를 반복하면서 prevMax와 currMax를 업데이트해 나간다. currMax는 prevMax(i-2)와 현재 값(i)을 더한 값과 currMax(i-1) 중 더 큰 값으로 업데이트되고 prevMax는 currMax를 저장한다. 사실상 dp와 마찬가지로 이전 두 집에서 훔칠 수 있는 최대 금액만 누적한다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  let prevMax = 0;
  let currMax = 0;

  for (let i = 0; i < nums.length; i++) {
    const temp = currMax
    currMax = Math.max(prevMax + nums[i], currMax)
    prevMax = temp
  }

  return currMax
};