(DP, Medium) House Robber

https://leetcode.com/problems/house-robber/description/

기본적으로 아이디어가 중요하다.
선택지는 2가지가 있다. 현재 인덱스를 터느냐/마느냐다.

DP로 풀 때 dp[i]는 i-1 값과 i-2 + (현재인덱스 amount) 중 큰 값으로 넣으면 된다.

i-1 값을 그대로 i에 세팅한다는 것은 현재 인덱스(i)를 털지 않겠다는 것이다.
i-2 + (현재인덱스 amount) 값을 i에 세팅한다는 것은 현재 인덱스(i)를 털겠다는 뜻이다.

그러므로 dp배열의 점화 과정에서는 위 값 중 max값(가장 많이 털 수 있는 선택지)를 세팅해 나가면 되는 것이다.

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(nums[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];
    }
}

또한 이 문제는 턴다/안턴다 선택지밖에 없으므로 변수 두 개를 두어 계속 누적한 뒤 둘 중 max값을 반환하는 방식으로 풀 수도 있다.

class Solution {
    public int rob(int[] nums) {
        int rob = 0;
        int norob = 0;
        for (int i = 0; i < nums.length; i ++) {
            int newRob = norob + nums[i];
            int newNoRob = Math.max(norob, rob);
            rob = newRob;
            norob = newNoRob;
        }
        return Math.max(rob, norob);
    }
}