💡 풀이
var rob = function (nums) {
let dp = [];
if (nums.length === 1) return nums[0];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
// i번째 집을 털었을 때 가질 수 있는 돈의 최댓값 = dp[i]
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
// console.log(dp);
return dp[dp.length - 1];
};📝 정리
기본 DP 문제로 볼 수 있다. DP 말고 다른 방법 중에 greedy..? swap? two pointers? 아직 내가 정확하게 이해를 하지 못한 방법이 하나 더 있는데 (더 간단하다) 그 방법은 아직 이해가 덜 됐기 때문에 여기서는 작성하지 않았다.
문제 요구사항을 보자. 당신은 도둑이다. 인접한 집의 돈을 도둑질하면 경찰에 신고하기 때문에 경찰에 신고당하지 않는 선에서 당신이 가장 많은 돈을 도둑질 했을 때 그 액수는 얼마인가? 라고 묻는 것이다. 풀이는 다음과 같다.
-
최댓값을 담을
dp배열의 첫번째 인덱스는 다음과 같이 정한다.dp[0] = nums[0]; -
i번째 집을 털었을 때 가질 수 있는 돈의 최댓값 =
dp[i]가 된다. -
이를 생각해보면, 인접 집은 도둑질을 할 수 없으니,
dp[i - 1], dp[i - 2] + nums[i], 즉dp[i-1]과dp[i-2] + nums[i]중 더 큰 값이 최댓값이 된다.
수정, 지적을 환영합니다!
문제 링크
https://leetcode.com/problems/house-robber/
