[Leetcode] House Robber (DP) - java

House Robber - LeetCode

문제 파악

강도들이 각 집을 돌면서 돈을 털려고 한다. 각 집에서는 돈이 존재함.

보안 시스템으로 인해서 인접한 두 집을 연속으로 털 수 없음.

최대로 털 수 있는 돈의 금액을 구하는 문제

---

접근 방법

DP를 이용해서 구현할 수 있는 문제이다.

인접하면 안되기 때문에 dp배열을 이용해서 금액을 더하면서 진행한다. dp[i] = dp[i-2] + nums[i] 로 구현했더니 문제가 발생했다.

무조건 2칸씩 떨어지게 저장하니까 [2,1,1,2] 와 같은 테스트 케이스에서 실패한다. 왜냐하면 최대 금액은 4 이기 때문에!!

따라서 dp[i-1]이 dp[i-2] + nums[i]보다 클 경우를 체크해줘야만 한다.

또한 nums의 길이가 1일 경우에 dp에 nums[1]을 저장할 수 없기 때문에 1인 경우를 예외처리 해줬다.

 

 

추가로 메모이제이션을 활용한 Top-down 방식으로도 풀어보았다.

1. 종료 조건을 설정한다.
2. memo에 저장된 값이 없으면 값을 점화식으로 계산한다.
3. memo[n-1] 을 반환

---

코드 구현

1. Bottom-up 방식

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

        int[] dp = new int[n];

        if(n == 1) return nums[0]; // 1일 때 예외처리
        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];
    }
}

2. Top-down 방식

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

        Map<Integer, Integer> memo = new HashMap<>();

        return dp(n-1, memo, nums);

    }
    public int dp(int n, Map<Integer, Integer> memo, int[] nums){
        if(n < 0) return 0;
        if(n == 0) return nums[0];

        if(!memo.containsKey(n)){
            memo.put(n, Math.max(dp(n-1, memo, nums), dp(n-2, memo, nums) + nums[n]));
        }

        return memo.get(n);
    }
}

---

배우게 된 점

그냥 어렵다… 점화식이 도저히 생각이 안난다…

많이 푸는 수 밖에…