https://leetcode.com/problems/house-robber/
dfs(재귀)+메모이제이션(top-down) / dp(bottom-up) / 공간 최적화 DP 방식으로 풀어보았다.
간단한 선형 동적 계획법(linear DP) 유형의 문제이다.
이 유형에 대해 연습하기 좋은 문제이다.
// var rob = function(nums) {
// function dfs(n) {
// if (n >= nums.length) return 0;
// return Math.max(nums[n] + dp(n + 2), dp(n + 1));
// }
// return dfs(0);
// };
//top-down . 큰 값을 작은 값으로부터 구하기
// var rob = function(nums){
// const memo = new Object();
// function dfs(n){
// if(n >= nums.length) return 0;
// if(memo[n] !== undefined) return memo[n]\
// memo[n] = Math.max(nums[n] + dfs(n+2),dfs(n+1))
// return memo[n]
// }
// return dfs(0)
// }
//bottom up. 작은 것을 큰것으로부터 구하기
// var rob = function(nums){
// const dp = new Array(nums.length+1)
// dp[0] = 0;
// dp[1] = nums[0];
// for(let i = 2;i<nums.length+1;i++){
// dp[i] = Math.max(nums[i-1]+dp[i-2],dp[i-1])
// }
// return dp[nums.length]
// }
//bottom-up으로 하고 메모리 사용 안하기. prev와 curr 값을 갱신하기
var rob = function (nums){
let prev = 0;
let curr = 0;
for(let i = 0; i<nums.length;i++){
let tempPrev = prev
prev = curr;
curr = Math.max(tempPrev + nums[i],curr)
}
return curr
}연관 문제
-
Maximum Product Subarray (Medium)
https://leetcode.com/problems/maximum-product-subarray/ (nwthomas.medium.com, leetcode.com) -
House Robber II (Medium)
https://leetcode.com/problems/house-robber-ii/ (leetcode.com) -
Paint House (Medium)
https://leetcode.com/problems/paint-house/ (leetcode.com) -
Paint Fence (Medium)
https://leetcode.com/problems/paint-fence/ (leetcode.ca, leetcode.com) -
House Robber III (Medium)
https://leetcode.com/problems/house-robber-iii/ (leetcode.com) -
Non-negative Integers without Consecutive Ones (Hard)
https://leetcode.com/problems/non-negative-integers-without-consecutive-ones/ -
Coin Path (Hard)
https://leetcode.com/problems/coin-path/ -
Delete and Earn (Medium)
https://leetcode.com/problems/delete-and-earn/ -
Solving Questions With Brainpower (Medium)
https://leetcode.com/problems/solving-questions-with-brainpower/ -
Count Number of Ways to Place Houses (Medium)
https://leetcode.com/problems/count-number-of-ways-to-place-houses/ -
House Robber IV (Medium)
https://leetcode.com/problems/house-robber-iv/ -
Mice and Cheese (Medium)
https://leetcode.com/problems/mice-and-cheese/ -
Largest Element in an Array after Merge Operations (Medium)
https://leetcode.com/problems/largest-element-in-an-array-after-merge-operations/
