[LeetCode#198] House Robber

 

❐ Description

---

문제 링크	https://leetcode.com/problems/house-robber/description/
난이도	Medium(실버2~1)

최초에 DFS로 풀이를 했었는데 Time Limit Exceed가 발생했다. 이 문제를 해결하는 과정에서 Memoization을

다시 제대로 학습하게 됐으며, 이 문제를 시작으로 보다 다양한 DP 문제를 풀어봐야겠다.

 

 

 

 

 

❐ Solutions

---

1. Reculsive Ⅰ - Time Limit Exceed

public class Solution {

    private int answer = 0;

    public int rob(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            dfs(i + 2, nums, nums[i]);
        }
        return answer;
    }

    public void dfs(int startIdx, int[] nums, int prev) {
        if (startIdx > nums.length - 1) {
            answer = Math.max(answer, prev);
            return;
        }

        if (startIdx == nums.length - 1) {
            answer = Math.max(answer, prev + nums[startIdx]);
            return;
        }

        for (int i = startIdx; i < nums.length; i++) {
            dfs(i + 2, nums, nums[i] + prev);
        }
    }
}

 

2. Reculsive Ⅱ - Time Limit Exceed

public class Solution {
    public int rob(int[] nums) {
        return rob(nums, nums.length - 1);
    }
    
    private int rob(int[] nums, int i) {
        if (i < 0) return 0;
        return Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
    }
}

• `rob(nums, i - 2) + nums[i]` :  `i`번째 집을 턴 경우
• `rob(nums, i - 1)` : `i`번째 집을 털지 않은 경우

 

3. Reculsive + Memoization(top-down)

public class Solution {

    private int[] memo;
    
    public int rob(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        return rob(nums, nums.length - 1);
    }

    private int rob(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo[i] != -1)return memo[i];
        memo[i] = Math.max(rob(nums, i - 2) + nums[i], rob(nums, i - 1));
        return memo[i];
    }
    
}

 

 

4. Iterative + memo (bottom-up)

public class Solution {
    
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        
        int[] memo = new int[nums.length + 1];
        memo[0] = 0;
        memo[1] = nums[0];
        
        for (int i = 2; i <= nums.length; i++) {
            memo[i] = Math.max(nums[i - 1] + memo[i - 2], memo[i - 1]);
        }
       
        return memo[nums.length];
    }

}

 

 

5. Iterative + two variables (bottom-up) 

public class Solution {
    
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        
        // prev2 = 두 집 전까지의 최대 금액
        // prev1 = 바로 직전 집까지의 최대 금액
        int prev2 = 0; prev1 = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            // current = 현재(i번째) 집을 털거나, 털지 않는 두 경우의 최대값.
            int current = Math.max(nums[i] + prev2, prev1);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
    
}

• prev2 ⇨ 두 집 전까지의 최대 금액
• prev1 ⇨ 바로 직전 집까지의 최대 금액
• current ⇨ 현재(i번째) 집을 털거나, 털지 않는 두 경우의 최댓값

 

 

 

 

 

---