House Robber - Python Solution

1. Introduction

The "House Robber" problem is a popular dynamic programming challenge that deals with optimizing profit in a scenario with constraints. It poses a situation where a robber aims to maximize the theft from a series of houses, with the condition that adjacent houses cannot be robbed on the same night. This problem tests the ability to analyze and apply dynamic programming for optimal decision-making.

Problem

Given an integer array nums, where each element represents the amount of money at each house, the task is to return the maximum amount of money that can be robbed tonight without alerting the police. The constraint is that adjacent houses cannot be robbed on the same night.

2. Solution Steps

1. Recognize the problem as an optimization problem that can be solved using dynamic programming.

2. Use an array dp to store the maximum amount that can be robbed up to each house.

3. Iterate through the houses, calculating the maximum robbery amount at each step.

4. For each house, consider two scenarios: robbing this house or skipping it.

5. The maximum amount for the current house is the max of (current house's money + max amount till the house before the previous one) and (max amount till the previous house).

6. Continue this process for all houses and return the maximum amount that can be robbed from all houses.

3. Code Program

def rob(nums):
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    dp = [0] * len(nums)
    dp[0], dp[1] = nums[0], 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]

# Example Usage
print(rob([1, 2, 3, 1]))
print(rob([2, 7, 9, 3, 1]))

Output:

4
12

Explanation:

1. Dynamic Programming Array: dp holds the maximum robbery amount at each step.

2. Base Cases: Initialize for the first two houses as they have no previous adjacent houses.

3. Iterative Calculation: For each house from the third onwards, calculate the maximum amount considering whether to rob this house or not.

4. Robbery Decision: The decision to rob a house is based on whether robbing it leads to a higher total than skipping it.

5. Maximum Calculation: At each house, the maximum robbery amount is updated in the dp array.

6. Final Result: dp[-1] gives the maximum amount that can be robbed from all houses.