198. House Robber

Problem Statement

link: https://leetcode.com/problems/house-robber/ https://leetcode.cn/problems/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 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.

Example:

Input: nums = [1,2,3,1] Output: 4

Input: nums = [2,7,9,3,1] Output: 12

Solution Approach

To maximize the total amount robbed, we can use a dynamic programming approach where we track the maximum value at each house considering the houses before

Algorithm

1. Initialize a tracking array dp with the first house’s value.
2. For each subsequent house, decide between robbing or skipping based on maximum potential earnings.
3. Return the last value in dp for the maximum robbery amount.

Implement

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

    
    

Twitter  facebook  Email