leetcode 198 java dp

/*
당신은 전문 강도로, 길을 따라 있는 집들을 털 계획을 세우고 있습니다. 
각 집에는 일정한 금액의 돈이 숨겨져 있으며, 
유일한 제약은 서로 인접한 두 집을 같은 날 털면 보안 시스템이 작동하여 경찰이 자동으로 출동한다는 것입니다.

정수 배열 nums가 주어지며, 이는 각 집에 숨겨진 돈의 금액을 나타냅니다. 
경찰을 경고하지 않으면서 오늘 밤에 훔칠 수 있는 최대 금액을 반환하세요.
*/

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 Math.max(nums[0], nums[1]);
        }
        else if(nums.length == 3) {
            return Math.max(nums[1], nums[0] + nums[2]);
        }

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

        return Math.max(dp[nums.length-1], dp[nums.length-2]);
    }
}

 

 

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.

 

 

인접한 곳은 털수 없다는 조건이 붙어있는 전형적인 dp 문제이다.

 

그렇기에 전 house 를 터는게 아니라, 전전 house 나 전전전 house 까지의 값이 현재값에 영향이 온다고 볼수 있다.

점화식은 다음과 같다.

 

dp[i] = Math.max(nums[i]+dp[i-2],nums[i]+dp[i-3]);

 

 

시간복잡도는 o(n) 이다.