HomeLeetcode198. House Robber - Leetcode Solutions
Leetcode

198. House Robber – Leetcode Solutions

Declan Clarke

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.

Examples:

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.

Solution in Python

Approach:

  1. Problem Breakdown:
    • You cannot rob two adjacent houses.
    • The goal is to find the maximum amount of money you can rob.
  2. Dynamic Programming Idea:
    • We’ll maintain a dynamic programming (DP) array where dp[i] represents the maximum amount of money you can rob up to house i.
    • For each house i, you have two options:
      1. Rob the house: If you rob house i, then you add the money from house i to the maximum amount of money robbed from houses up to i-2 (dp[i-2]).
      2. Do not rob the house: If you don’t rob house i, then the maximum money you can have up to house i is the same as the maximum money up to house i-1 (dp[i-1]).
    • The recurrence relation is:
      dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  3. Base Cases:
    • If there’s only one house, the maximum money is simply the amount in that house.
    • If there are two houses, you rob the house with the larger amount of money.
  4. Final Answer:
    • The answer will be in dp[-1], which represents the maximum amount of money that can be robbed from all houses.
Python
class Solution:
    def rob(self, nums: List[int]) -> int:
        # Edge case: if there are no houses
        if not nums:
            return 0
        
        n = len(nums)
        
        # Edge case: if there's only one house
        if n == 1:
            return nums[0]
        
        # DP array to store the maximum money that can be robbed up to each house
        dp = [0] * n
        
        # Base cases
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        # Fill the DP array using the recurrence relation
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        # The answer will be in the last element of dp array
        return dp[-1]

Explanation of the Code:

  1. Edge Case Handling:
    • If nums is empty, return 0 as there are no houses to rob.
    • If there’s only one house, return the amount in that house.
  2. Dynamic Programming Array Initialization:
    • Initialize a dp array of the same length as nums.
    • Set dp[0] to nums[0] (robbing the first house).
    • Set dp[1] to the maximum of the first two houses, as you can only rob one of them.
  3. Filling the DP Array:
    • Iterate over the array starting from the third house (index 2) and apply the recurrence relation to fill the dp array.
  4. Result:
    • The last element of the dp array (dp[-1]) contains the maximum amount of money that can be robbed from all houses.

This approach efficiently computes the result in O(n) time with O(n) space, which is optimal given the constraints.

Solution in Javascript

JavaScript
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    // Edge case: If there are no houses, the maximum money you can rob is 0.
    if (nums.length === 0) return 0;
    
    // Edge case: If there's only one house, the maximum money you can rob is the amount in that house.
    if (nums.length === 1) return nums[0];
    
    // Create a dynamic programming (dp) array where dp[i] represents the maximum
    // amount of money that can be robbed up to house i.
    let dp = new Array(nums.length);
    
    // Base cases:
    dp[0] = nums[0]; // If we only rob the first house.
    dp[1] = Math.max(nums[0], nums[1]); // The maximum of robbing the first house or the second house.
    
    // Fill the dp array using the recurrence relation.
    for (let i = 2; i < nums.length; i++) {
        // For each house i, decide whether to rob it or not:
        // - If we rob house i, we add its amount to dp[i-2] (max money from houses up to i-2).
        // - If we don't rob house i, the max money up to house i is just dp[i-1].
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
    }
    
    // The last element of the dp array contains the maximum money that can be robbed from all houses.
    return dp[dp.length - 1];
};

Solution in Java

Java
class Solution {
    public int rob(int[] nums) {
        // Edge case: If there are no houses, the maximum money you can rob is 0.
        if (nums.length == 0) return 0;

        // Edge case: If there's only one house, the maximum money you can rob is the amount in that house.
        if (nums.length == 1) return nums[0];

        // Create a dynamic programming (dp) array where dp[i] represents the maximum
        // amount of money that can be robbed up to house i.
        int[] dp = new int[nums.length];

        // Base cases:
        dp[0] = nums[0]; // If we only rob the first house.
        dp[1] = Math.max(nums[0], nums[1]); // The maximum of robbing the first house or the second house.

        // Fill the dp array using the recurrence relation.
        for (int i = 2; i < nums.length; i++) {
            // For each house i, decide whether to rob it or not:
            // - If we rob house i, we add its amount to dp[i-2] (max money from houses up to i-2).
            // - If we don't rob house i, the max money up to house i is just dp[i-1].
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        // The last element of the dp array contains the maximum money that can be robbed from all houses.
        return dp[dp.length - 1];
    }
}

Solution in C#

C#
public class Solution {
    public int Rob(int[] nums) {
        // Edge case: If there are no houses, the maximum money you can rob is 0.
        if (nums.Length == 0) return 0;

        // Edge case: If there's only one house, the maximum money you can rob is the amount in that house.
        if (nums.Length == 1) return nums[0];

        // Create a dynamic programming (dp) array where dp[i] represents the maximum
        // amount of money that can be robbed up to house i.
        int[] dp = new int[nums.Length];

        // Base cases:
        dp[0] = nums[0]; // If we only rob the first house.
        dp[1] = Math.Max(nums[0], nums[1]); // The maximum of robbing the first house or the second house.

        // Fill the dp array using the recurrence relation.
        for (int i = 2; i < nums.Length; i++) {
            // For each house i, decide whether to rob it or not:
            // - If we rob house i, we add its amount to dp[i-2] (max money from houses up to i-2).
            // - If we don't rob house i, the max money up to house i is just dp[i-1].
            dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        // The last element of the dp array contains the maximum money that can be robbed from all houses.
        return dp[dp.Length - 1];
    }
}

Related Post

Subscribe
Notify of

0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com