LeetCode 198. House Robber (javascript solution)

Description:

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 houses have security systems conn…


This content originally appeared on DEV Community and was authored by codingpineapple

Description:

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 houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

var rob = function(nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0]

    // Keep track of the max money we can make with x amount of houses available
    // dp[0] = max amount if we only have the first house to rob
    // dp[1] = max amount if we only have the first 2 houses to rob
    let dp = [nums[0], Math.max(nums[0], nums[1])];

    for (let i = 2; i < nums.length; i++) {
        // Compare current max with the previous max
        // Check if the money from the current house + max of 2 houses away is greater than the current max
        dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
    }
    return dp[nums.length - 1];
};


This content originally appeared on DEV Community and was authored by codingpineapple


Print Share Comment Cite Upload Translate
APA
codingpineapple | Sciencx (2022-10-06T02:38:13+00:00) » LeetCode 198. House Robber (javascript solution). Retrieved from https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/.
MLA
" » LeetCode 198. House Robber (javascript solution)." codingpineapple | Sciencx - Sunday May 2, 2021, https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/
HARVARD
codingpineapple | Sciencx Sunday May 2, 2021 » LeetCode 198. House Robber (javascript solution)., viewed 2022-10-06T02:38:13+00:00,<https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/>
VANCOUVER
codingpineapple | Sciencx - » LeetCode 198. House Robber (javascript solution). [Internet]. [Accessed 2022-10-06T02:38:13+00:00]. Available from: https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/
CHICAGO
" » LeetCode 198. House Robber (javascript solution)." codingpineapple | Sciencx - Accessed 2022-10-06T02:38:13+00:00. https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/
IEEE
" » LeetCode 198. House Robber (javascript solution)." codingpineapple | Sciencx [Online]. Available: https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/. [Accessed: 2022-10-06T02:38:13+00:00]
rf:citation
» LeetCode 198. House Robber (javascript solution) | codingpineapple | Sciencx | https://www.scien.cx/2021/05/02/leetcode-198-house-robberjavascript-solution/ | 2022-10-06T02:38:13+00:00
https://github.com/addpipe/simple-recorderjs-demo