LeetCode #198: House Robber

LeetCode Solutions

https://leetcode.com/problems/house-robber/

To solve this problem, we will use dynamic programming, where we will create a dp list to store the maximum amount of money we can get from robbing the houses. We will start by robbing the first house and store its amount in the dp list. Then we will rob the second house and store its amount in the dp list as well. From there, we will iterate through the list starting from the third house and calculate the maximum amount of money we can get by either robbing the current house and the one before the previous house or just robbing the previous house. We will store the maximum amount of money in the dp list.

Finally, we will return the last element in the dp list, which represents the maximum amount of money we can get from robbing the houses.

Algorithm:

  1. If the nums list is empty, return 0.
  2. If the nums list has only one house, return the amount of money in that house.
  3. If the nums list has only two houses, return the maximum amount of money from the two houses.
  4. Create a dp list of the same length as nums.
  5. Store the amount of money in the first house in the dp list.
  6. Store the maximum amount of money from the first two houses in the dp list.
  7. Iterate through the nums list starting from the third house: a. Calculate the maximum amount of money we can get from robbing the current house and the one before the previous house or just robbing the previous house. b. Store the maximum amount of money in the dp list.
  8. Return the last element in the dp list, which represents the maximum amount of money we can get from robbing the houses.

Here’s the Python code that implements the above algorithm:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        len_nums = len(nums)
        if len_nums == 1:
            return nums[0]
        elif len_nums == 2:
            return max(nums[0], nums[1])
        dp = [0] * (len_nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        for i in range(2, len_nums):
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])
        return dp[-1]

Time Complexity

The time complexity of this solution is O(n), where n is the length of the nums list. This is because we iterate through the nums list only once.

Space Complexity

The space complexity of this solution is O(n), where n is the length of the nums list. This is because we create a dp list of the same length as nums.