House Robber

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

House Robber - LeetCode

 

주어진 배열의 값이 집의 돈이라고 할 때, 연속된 집을 훔칠 수 없다면 최선으로 훔쳤을 때의 최대 돈의 값을 계산하는 문제이다. DP 문제로 해결할 수 있으며 점화식을 세워야 한다.

연속되지 않는 것이 중요하기 때문에 특정 위치 n 에서 최대로 훔칠 수 있는 돈은

1. n - 1일까지 최대로 훔치고 n일차에 훔치지 않은 경우
2. n - 2 일차에 훔치고 n - 1 일차에 훔치지 않은 후에 n 일차에 훔치는 경우이다

n - 2 일차를 기준으로 해야 하기에 1일차, 2일차의 경우 조건이 바뀐다.

1. 1일차의 경우 바로 그날을 훔치는 경우
2. 2일차의 경우 1일차에 훔치거나 2일차에 훔치거나이다

문제 조건에서 n = 1부터 가능하므로 이를 if문으로 예외 처리해주고 점화식을 세웠다. 최종적으로 배열의 마지막 값(마지막 날)을 리턴해주면 된다.

public class Solution {  
    public int rob(int[] nums) {  
  
        int[] dp = new int[nums.length];  
        dp[0] = nums[0];  
        if(nums.length == 1) return dp[0];  
  
        dp[1] = Math.max(nums[1], dp[0]);  
        if(nums.length == 2) return 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];  
    }  
}