PS/LeetCode
LeetCode / Dynamic Programming / 198번 / House Robber / JS
KimMinJun
2023. 5. 14. 19:13
House Robber - LeetCode
Can you solve this real interview question? House Robber - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent ho
leetcode.com
< 문제 간단설명 >
도둑이 연속해서 인접한 두 집을 연속해서 도둑질하면 경찰에게 걸린다. 따라서 인접한 두 집을 연속해서 도둑질 하지 않는다고 할 때 가장 많이 도둑질 했을때의 돈을 반환한다.
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function (nums) {
// 연속해서 두 집을 훔칠 수 없기 때문에 가장 큰 값 반환
if (nums.length <= 2) {
return Math.max(...nums);
}
// dp[index] = index 번 째 집을 도둑질 했을 때 얻을 수 있는 최댓값
let dp = Array.from({ length: nums.length }, () => 0);
dp[0] = nums[0]; // 0번째 집을 털었을 때 얻을 수 있는 최댓값은 0번째만 털 수 있음
dp[1] = nums[1]; // 1번째 집은 0번째 집을 털 수 없으므로 1번째 집만 털었을 때 최댓값
dp[2] = dp[0] + nums[2]; // 2번째 집은 1번째 집을 털 수 없으므로 0번째 값과 더해줌
// i번째는 i-1번째와 연속으로 털 수 없기 때문에,
// i-2와 i-3번째 중 최댓값과 i번째 값을 더해줌
for (let i = 3; i < nums.length; i += 1) {
dp[i] = Math.max(dp[i - 3], dp[i - 2]) + nums[i];
}
return Math.max(...dp);
};