[java] House Robber

[참고문제] : https://leetcode.com/problems/house-robber/

 

 

House Robber - LeetCode

문제 풀이

DP 문제다.

점화식을 찾기 위해서 나열해보자.

이번에도 꽤 많이 나열해보았다.

 

생각의 흐름 - 초깃값 찾기

이번에도 초깃값부터 찾아보았다.

arr[n] 부터 생각해보았으나, 역시 최초 1일때부터 고민하는 것이 나았다.

6번째 정도 적어보니, 이전에 적어둔 식들이 다시 쓰이기 시작했다.

현재 들어온 값과 2칸전에 확인한 MAX값을 더하거나, 1칸 전의 MAX값을 비교하는 것이다.

public int rob(int[] nums) {
    int arr[] = new int[101];

    int len = nums.length;
    if(len == 1)
        return nums[0];
    else if(len == 2)
        return Math.max(nums[0], nums[1]);
    else if(len == 3)
        return Math.max(nums[0] + nums[2], nums[1]);
    else if(len == 4)
        return Math.max(Math.max(nums[0] + nums[2], nums[1] + nums[3]), nums[0] + nums[3]);
    arr[0] = nums[0];
    arr[1] = Math.max(nums[0], nums[1]);
    arr[2] = Math.max(nums[0] + nums[2], nums[1]);
    arr[3] = Math.max(Math.max(nums[0] + nums[2], nums[1] + nums[3]), nums[0] + nums[3]);

    for(int i = 4; i < len; i++) {
        arr[i] = Math.max(arr[i-2] + nums[i], arr[i-1]);
    }
    return arr[len-1];
}

 

수정

그렇게 많은 작업을 할 필요 없다.

class Solution {
    public int rob(int[] nums) {
        int[] dp = new int[nums.length];       
        if(nums.length == 1)
            return nums[0];
        else if(nums.length == 2) {
            return nums[0] > nums[1] ? nums[0]:nums[1];
        }
        else {
            dp[0] = nums[0];
            dp[1] = nums[0] > nums[1] ? nums[0]:nums[1];

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

            return dp[nums.length - 1]; 
        }
    }
}