LeetCode 198 - House Robber

House Robber - LeetCode

 

인접한 두 집을 털 수는 없다.

[1, 2, 3, 1]이라면 0번과 2번을 털면 4라는 최대 수익을 낼 수 있다.

즉 해당 위치의 집을 털거나 털지 않거나 둘 중 하나의 경우가 존재한다.

i위치에서의 최대는 i-1을 털었을 떄와 i-2를 털고 i를 털었을 때의 최대가 된다.

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

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

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