Dynamic Programming House Robber

0/1 Dynamic Programming Overview

The 0/1 Dynamic Programming (DP) pattern is used to solve problems where each item can be either included or excluded (picked or not picked) from a solution. This is common in problems like the classic Knapsack and House Robber.

Key Characteristics

• Binary Choice: For each element, you decide to take it (1) or leave it (0).
• Optimal Substructure: The solution to the problem can be constructed from solutions to its subproblems.
• Overlapping Subproblems: The same subproblems are solved multiple times.

House Robber Problem

Given a row of houses, each with some amount of money, you cannot rob two adjacent houses. Find the maximum amount you can rob.

State Definition

Let dp[i] be the maximum amount you can rob from the first i houses.

Recurrence Relation

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

• dp[i-1]: Skip the current house.
• dp[i-2] + nums[i]: Rob the current house and add its value to the best solution two houses before.

Base Cases

dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Example Code (Python)

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    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(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

Space Optimization

Since dp[i] only depends on the previous two values, you can reduce space to O(1):

def rob(nums):
    prev, curr = 0, 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

The 0/1 DP pattern is foundational for many competitive programming problems. Mastering it will help you tackle a wide range of algorithmic challenges!