[LeetCode] 198. House Robber

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

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.

Example 2:

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

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

---

Solution

class Solution {
    public int rob(int[] nums) {
        if (nums.length < 3)
            return nums.length == 1 ? nums[0] : Math.max(arr[arr.length - 1], arr[arr.length - 2]);
        int[] arr = new int[nums.length];
        arr[0] = nums[0];
        arr[1] = nums[1];
        arr[2] = nums[0] + nums[2];
        for (int i = 3; i < nums.length; i++) {
            arr[i] = Math.max(arr[i - 2], arr[i - 3]) + nums[i];
        }
        return Math.max(arr[arr.length - 1], arr[arr.length - 2]);
    }
}

Explanation

• 배열의 길이에 따라 선택해야 하는 경우의 수는 다음과 같다.

|길이|배열(인덱스)|경우의 수| |:—:|:—|:—| |2|0, 1|max(0, 1)| |3|0, 1, 2|max(0 + 2, 1)| |4|0, 1, 2, 3|max(max(0 + 2, 0 + 3), 1 + 3)| |5|0, 1, 2, 3, 4|max(0 + 2 + 4, max(1 + 3, 1 + 4))| |6|0, 1, 2, 3, 4, 5|max(0 + max(2 + 5, 3 + 5), 1 + 3 + 5) |7|0, 1, 2, 3, 4, 5, 6|max(0 + max(2 + 4 + 6, max(3 + 5, 3 + 6)), 1 + max(max(3 + 5, 3 + 6), 4 + 6)))| |…|…|…|

• 위의 경우의 수에서 알 수 있듯이 외부 max()속 내부 max()를 계산하면 결국 두 가지 경우의 수 중 하나를 선택하게 된다. 그리고 두 가지 경우의 수는 배열의 첫 번째 요소를 선택하거나 두 번째 요소를 선택하는 것에서 부터 시작되는 것을 알 수 있다.
• 외부 max()속 내부 max()를 계산하기 위해서는 주어진 배열을 작은 배열로 나누어 계산해야 한다. 그리고 구해진 값을 메모하고 외부 max()값을 구하는데 활용해야 한다.
• 먼저, 배열의 길이가 3미만인 경우는 특별한 계산이 필요하지 않으므로 간단히 if조건문을 작성해 해결한다.

  if (nums.length < 3)
    return nums.length == 1 ? nums[0] : Math.max(arr[arr.length - 1], arr[arr.length - 2]);
  

• 내부 max()의 값을 메모하기 위하여 배열 arr을 선언한다.

  int[] arr = new int[nums.length];
  

• 배열 arr의 인덱스는 배열 nums의 인덱스에서 선택할 수 있는 가장 큰 값이 할당되도록 할 것이므로, 계산이 필요 없는 인덱스 0 ~ 2에 미리 값을 할당해준다.

  arr[0] = nums[0];
  arr[1] = nums[1];
  arr[2] = nums[0] + nums[2];
  

• 인덱스 3부터 내부 max()의 값을 계산하고, 해당 값을 배열 arr에 기록하면서 for반복문을 진행하도록 한다.

  for (int i = 3; i < nums.length; i++) {
    arr[i] = Math.max(arr[i - 2], arr[i - 3]) + nums[i];
  }
  

• 값이 할당된 배열 arr의 마지막 요소 혹은 마지막 이전 요소 중 큰 값이 문제에서 요구하는 반환값이 된다.

  return Math.max(arr[arr.length - 1], arr[arr.length - 2]);