[Leetcode] House Robber (DP) - java

House Robber - LeetCode

문제 파악

인접한 두 집을 털면 신고가 들어감.

즉, 떨어져 있는 집을 털어야 하는데 이 금액이 최대가 되어야 하는 문제

---

접근 방법

dp[0]에 n/2까지 반복하는걸로 초기화 해야하나..? → 굳이 할 필요가 없음.

dp[i]는 i번 째까지 털 수 있는 최대 금액을 저장

dp[0] = nums[0]

dp[1] = max(nums[0], nums[1])

 

1. 첫번째, 두번째 집에서 털 수 있는 값을 저장
2. i-1번째와 i-2번째와 i번째의 금액을 더한 것을 비교해서 더 큰 값으로 갱신 → 인접할 수 없기 때문에 i-1까지의 값과 비교
3. 값이 0이거나 하나일 경우에 예외처리

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

---

코드 구현

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        // 예외처리
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        // i번째까지 털 수 있는 금액 저장
        int[] dp = new int[n];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]); 

        // 금액 갱신
        for(int i = 2; i < n; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[n - 1];
    }
}