[leetcode 75 198.House Robber] - DP, Math.max

문제

https://leetcode.com/problems/house-robber/?envType=study-plan-v2&envId=leetcode-75

당신은 거리의 집을 털려는 전문 강도입니다. 각 집에는 일정 금액의 돈이 숨겨져 있습니다. 각각의 집에서 물건을 강탈하는 것을 막는 유일한 제약은 인접한 집에 보안 시스템이 연결되어 있고 같은 밤에 인접한 두 집에 침입한 경우 자동으로 경찰에 연락한다는 것입니다 .

nums각 집의 금액을 나타내는 정수 배열이 주어지면 오늘 밤 경찰에 신고하지 않고 훔칠 수 있는 최대 금액을 반환하세요 .

 

예시 1:

입력: nums = [1,2,3,1]

 출력: 4

 설명: 1번 집(돈 = 1)을 털고 3번 집(돈 = 3)을 털었습니다.

도둑질할 수 있는 총 금액 = 1 + 3 = 4.

예 2:

입력: nums = [2,7,9,3,1]

 출력: 12

 설명: 도둑의 집 1(돈 = 2), 도둑의 집 3(돈 = 9) 및 도둑의 집 5(돈 = 1).

도둑질할 수 있는 총 금액 = 2 + 9 + 1 = 12.

예 3:

입력: nums = [2,1,1,2]

 출력: 4

제약:

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

코드

class Solution {
    public int rob(int[] nums) {
        // 길이가 1개일 경우 제약조건 참조
        if(nums.length == 1) return nums[0];
        // dp배열은 누적 값
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0],nums[1]);
        
        for(int i=2;i<nums.length;i++){
            // 현재위치에서 최대로 가져갈 수 있는 값은
            // 현 위치+누적금액 or 이전 위치
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[nums.length-1];
    }
}