198. House Robber
https://leetcode.com/problems/house-robber/
도둑이 빈집에 몰래 들어가 돈을 훔쳐서 나오려고 한다. 이때 이웃한 집에서 연속으로 돈을 훔치면 경찰에게 걸리게 된다. 경찰에게 걸리지 않고 최대로 훔칠 수 있는 돈은 얼마일까?
이 문제는 전형적인 DP 문제다. 1 ~ N번째 집까지 최적의 방법으로 돈을 훔쳐야 한다.
X번째 집에서 도둑이 할 수 있는 선택지는 두 가지이다.
돈을 훔치거나, 안 훔치거나.
마찬가지로 X-1번째 집에서도 도둑의 선택지는 두 가지이다. 나아가서 X-2, X-3, ... 1번째 집까지 모든 집에서 두 가지의 선택지를 가진다.
다시 돌아와서, X번째 집에서 돈을 훔치는 경우를 생각해보자.
X번째 집에서 돈을 훔치려면 X-1번째 집에서는 반드시 돈을 훔치지 않아야 한다.
따라서, X-1까지의 돈(X-1 제외) + X번째 집이 X번째 집에서 훔치기로 했을 때의 금액이다.
이번에는 X번째 집에서 돈을 훔치지 않는 경우를 생각해보자.
X번째 집에서 돈을 안 훔친다면, X-1번째 집에서 돈을 훔쳐야 가장 최적의 금액을 만들 수 있을 것이다.
따라서, X-1까지의 돈(X-1 포함)이 X번째 집에서 훔치지 않았을 때의 금액이다.
쉽게 이해하기 위해 X번째에서 돈을 훔쳤을 때를 sum[x][0], 훔치지 않았을 때를 sum[x][1]로 표현해보자.
sum[x][0] = sum[x-1][1] + money[x]
sum[x][1] = sum[x-1][0]이렇게 간단하게 수식으로 표현할 수 있다.
N번째 집까지 훔칠 수 있는 최대의 돈은 sum[n][0], sum[n][1] 둘 중 더 큰 값이 된다.
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) {
return nums[0];
}
int length = nums.length;
int [][]dp = new int[length][2];
dp[0][0] = nums[0];
dp[0][1] = 0;
dp[1][0] = nums[1];
dp[1][1] = nums[0];
for(int i=2;i<length;i++){
dp[i][0] = Math.max(dp[i - 2][0], dp[i - 1][1]) + nums[i];
dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1]);
}
return Math.max(dp[length - 1][0], dp[length - 1][1]);
}
}https://leetcode.com/submissions/detail/595401095/
https://github.com/sorious77/LeetCode/blob/main/code/198.java
