House Robber(Java,C++)

House Robber 문제는 정말 유명한 DP 문제이고 리트코드 안에서도 여러번 풀어봤다. 그런데 지금까지 나는 Memoization 방식으로 풀어봤고 이번에 문제집에서 줬던 가이드 순서대로 풀기 시작하니 되게 전보다 이해가 빨랐고 문제도 쉽게 풀었다.

이 문제에 핵심은 지금 집을 터느냐 / 털지않느냐로 갈려진다. 털게되는 선택을 할경우 바로 옆에 집은 털면 안되기 때문에 두칸전에 집을 털었을때까지 있었던 최고값과, 털지 않느냐 선택을 할때는 한칸전에 집이 털리기까지 최고값을 가지고 오면된다. 한칸 전에 집이 털리기전까지의 최고값을 가지고 와야하는데 이 부분을 이해 못하고 그냥 현재 값만 가지고 올려니깐 여러번 시행 착오가 있었다. 그래도 DP 마스터에 길에 계속 다가갈려고 노력중이다.

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0]; 
        if(nums.length == 2) return Math.max(nums[0],nums[1]); 

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


        return dp[nums.length-1]; 
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1) return nums[0]; 
        vector<int> dp(nums.size()); 
        dp[0] = nums[0]; 
        dp[1] = max(nums[0],nums[1]); 

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

        return dp[nums.size()-1]; 
    }
};