?? Problem-Solving w/ DP: House Robber (LeetCode) ??

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

How to maximize your loot without triggering alarms? That’s the gist of the House Robber problem on LeetCode. Here's the challenge:

You’re a professional robber planning to rob houses on a street ???♂?. Each house has a stash of cash, but the catch is that you can’t rob two adjacent houses—their security systems are linked. The goal? Figure out the maximum amount you can rob without getting caught. ??

?? My Solution:

To crack this, I used a dynamic programming approach:

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

Key Insights:

1?? If there’s only one house, rob it—no brainer!

2?? Update each house’s value to the maximum loot possible up to that point.

3?? For every house starting from the 3rd, you decide to:

• Rob this house + whatever you robbed two houses back.
• Or skip it and stick to the max from the previous house.

This greedy yet calculated approach ensures you squeeze out every last dollar without tripping alarms! ??

For example:

• Input: [2, 7, 9, 3, 1]
• Output: 12 (Rob houses 1, 3, and 5 for 2 + 9 + 1)

? Why I Love This Problem: It’s a classic mix of logic and optimization that reflects real-world decision-making (though hopefully not for actual robbing ??).