213. House Robber II

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

nums의 각 값은 집의 돈을 의미하고 훔치는 집은 연속해서 훔칠 수 없다. 집은 원형으로 이어져있어 첫번째 집과 마지막 집이 붙어있다.(하나만 훔칠 수 있다.)

Solution

Eval 2 cases DP

이미 House Robber I 에서 DP를 통해 집이 이어져 있지 않은 경우를 해결했다. 이번 문제도 간단히 조건을 추가한다면 I의 방식으로 풀 수 있다.
1. 첫번째 집을 훔치지 않을 경우: 두번째 ~ 마지막집을 I의 방식으로 푼다.
2. 마지막 집을 훔치지 않을 경우: 첫번째 ~ 마지막에서 두번째 집을 I의 방식으로 푼다.

Algorithm

• 문제를 위의 두 조건으로 나눈다. (slice)
• getMaxMoney 함수는 결과 arr를 만들고 iteration을 통해 훔칠 수 있는 최대 양을 구한다.

  result[i]는 i번째 집을 포함해 훔친 최대 금액
  result [i] = Math.max(result[i - 3], result[i - 2])

• 두 조건으로 나눈 두 문제를 getMaxMoney함수에 넣고 둘 중 큰 답을 반환한다.

var rob = function(nums) {
  // 2가지종류 1. 첫번째 집 rob => 마지막 집은 제거 2. 두번째 집 rob => 마지막 집 포함
  // 1: [1 ~ end] 2: [0 ~ end - 1]
  // include nums[i] and maximum
  const getMaxMoney = (newNums) => {
    if (newNums.length === 1) return newNums[0];
    const result = new Array(newNums.length);
    result[0] = newNums[0];
    result[1] = newNums[1];
    for (let i = 2; i < result.length; i++) {
      result[i] = Math.max(result[i - 2], i > 2 ? result[i - 3] : null) + newNums[i];
    }
    return Math.max(result[result.length - 2], result[result.length - 1]);
  }
  
  if (nums.length === 1) return nums[0];
  return Math.max(getMaxMoney(nums.slice(1)), getMaxMoney(nums.slice(0, nums.length - 1)));
};

이해하기 쉽도록 두개의 동작을 분리했지만 result 배열을 두 개 만들고 iteration을 통해 해결할 수도 있다. slice대신 index를 넘기는 방식으로도 풀 수 있다. slice 는 O(n)의 추가적인 공간과 시간을 사용한다.