[LeetCode] 198. House Robber

출처 : https://leetcode.com/problems/house-robber/

House Robber - LeetCode

 

아직 부족하다는 생각이 많이 든 문제였다. DP를 사용하였지만 솔루션을 보면 내가 짠 코드가 무색해진다. 어려운 난이도가 아니였지만 아래와 같은 아이디어를 적용하면 내가 짠 코드처럼 길게 적지 않아도 되는 것...! 이것이 DP가 아닐까?

 

 

내 코드 :

class Solution {
    public int rob(int[] nums) {
        int l = nums.length;
        int[] dp = new int[l];
        
        if (l == 1) return nums[0];
        else if (l == 2) return Math.max(nums[0], nums[1]);
        else {
            dp[0] = nums[0]; dp[1] = nums[1];
            dp[2] = Math.max(dp[1], dp[0] + nums[2]);
            
            if (l == 3) return Math.max(dp[2], dp[1]);
        
            for(int i=3; i<l; i++) {
                dp[i] = Math.max(nums[i] + dp[i-2], Math.max(nums[i] + dp[i-3], dp[i-1]));
            }
            /*
            for(int i=0; i<l; i++) {
                System.out.println(dp[i] + " ");
            }*/
            return Math.max(dp[l-1], dp[l-2]);
        }
    }
}

 

 

다른 사람 코드 : 

class Solution {
    public int rob(int[] nums) {
        int prev1 = 0;
        int prev2 = 0;
        for(int num : nums) {
            int dp = Math.max(prev1, prev2+num);
            prev2 = prev1;
            prev1 = dp;
        }

        return prev1;
    }
}