House Robber
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400
- 문제 분석
각 집마다 훔칠수 있는 돈이 있음 -> nums 배열
인접한 집은 동시에 털 수 없음
최대 얼마를 훔칠 수 있는지 구하는 문제
i번째 집까지 고려했을때, 최대 얼마까지 훔칠수있나
1. i번째 집을 털지 않는다 -> 그 전까지의 집의 최대값을 그대로 가져옴
2. I번째 집을 턴다 -> i-2번째 집까지의 최대값 + nums[i]
n번째 집까지 훔칠때의 최대 금액을 생각해보면 n번째 집을 훔치지 않는다면 n-1번째 집을 훔쳤을때의 최댓값과 같고, n번째 집을 훔친다면 바로 이전 집은 훔칠 수 없으니까 n-2번째 집을 훔쳤을때의 최댓값에 n번째 집의 금액을 더한 것이됨.
F(n)을 n번째 집까지 털었을때의 최댓값이라하면 다음 점화식이 성립됨
- 풀이 과정
n만큼 크기를 가진 memo배열을 만들어줌 <- dp는 이전 상태를 저장하고 최적의 상태를 구하는것(이전 상태를 저장하기 위한 배열)
memo배열을 NONE값으로 초기화 시켜주고 dp를 진행시켜줌
n이 0이라면 nums[0]값을 반환해주고, 1이라면 0과 1중에 더 큰값을 반환시켜줌
그리고 둘다 아니라면 두값중 더 큰 값을 n값에 넣을것임
1. 이번집 안털고 전집 최댓값
2. 이번집 털고 이전전집 최댓값 + 이번집
그래서 최종적으로 n값에 최적의 값이 들어오게되어짐.
최종 코드
class Solution {
static int NONE = Integer.MAX_VALUE;
public int rob(int[] nums) {
int[] memo = new int[nums.length];
Arrays.fill(memo, NONE);
return dp(memo, nums, nums.length-1);
}
public static int dp(int[] memo, int[] nums, int n) {
if(n==0) {
return nums[0];
}
if(n==1) {
return Math.max(nums[0], nums[1]);
}
if(memo[n] == NONE) {
memo[n] = Math.max(dp(memo, nums, n-1), // 이번집 안털고 전집 최대값
dp(memo, nums, n-2) + nums[n]); // 이번집 털고 이전전집 최댓값 + 이번집
}
return memo[n];
}
}