198. House Robber

• 각 집에 위치한 돈의 액수가 배열 nums 로 주어졌을 때 도둑이 획득할 수 있는 가장 많은 액수를 구하는 문제. 단, 연속된 2개의 집을 방문하게되면 경보 시스템이 울려서 잡힐 수 있다.

• 결국 현재 집을 방문했을 때 도둑의 선택지는 두가지가 된다.
• 이전 집을 방문 robbed = 1 했다면, 현재 집에서 돈을 획득할 수 없고 건너뛴 것으로 표시 robbed = 0 해야 한다.
• 이전 집을 방문하지 않았다 robbed = 0다면, 현재 집에서 돈 nums[index] 을 획득하고 상태를 표시 robbed = 1 한다.

• 상태 값을 이전 집의 방문 여부 robbed = 0 or 1 및 위치 index 에 따라 저장 dp[robbed][index] 하고 이미 계산된 값은 다시 계산하지 않고 활용한다.

class Solution {
    int traverse(int[] nums, int[][] dp, int index, int robbed) {
        if (index >= nums.length) return 0;
        if (dp[robbed][index] != -1) return dp[robbed][index];

        int result = traverse(nums, dp, index + 1, 0);
        if (robbed == 0) {
            result = Math.max(
                result, 
                traverse(nums, dp, index + 1, 1) + nums[index]);
        }
        return dp[robbed][index] = result;
    }

    public int rob(int[] nums) {
        int[][] dp = new int[2][nums.length];
        Arrays.fill(dp[0], -1);
        Arrays.fill(dp[1], -1);
        return traverse(nums, dp, 0, 0);
    }
}