101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Dynamic Programming Approach - Complex approach
  2. Space-Optimized Dynamic Programming - Complex approach
  3. Recursive Approach with Memoization - Complex approach

Approach 1: Dynamic Programming Approach

The key insight for solving this problem is to use dynamic programming to track the maximum amount of money we can rob up to each house.

Let's define dp[i] as the maximum amount of money we can rob up to the i-th house. We have two options for each house:

  1. Rob the current house: dp[i] = dp[i-2] + nums[i]
  2. Skip the current house: dp[i] = dp[i-1]

We choose the option that gives us the maximum amount: dp[i] = max(dp[i-2] + nums[i], dp[i-1]).

The base cases are:

  • dp[0] = nums[0] (if there's only one house, we rob it)
  • dp[1] = max(nums[0], nums[1]) (if there are two houses, we rob the one with more money)

Algorithm:

  1. Initialize an array dp of size n, where dp[i] represents the maximum amount of money we can rob up to the i-th house.
  2. Set the base cases: dp[0] = nums[0] and dp[1] = max(nums[0], nums[1]).
  3. Iterate from i = 2 to n-1:
  4. a. Calculate dp[i] = max(dp[i-2] + nums[i], dp[i-1]).
  5. Return dp[n-1] as the maximum amount of money we can rob.

Time Complexity:

O(n)

Where n is the number of houses. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(n)

We use an array of size n to store the maximum amount of money we can rob up to each house.

Approach 2: Space-Optimized Dynamic Programming

We can optimize the space complexity of the dynamic programming approach by observing that we only need the results from the previous two houses to calculate the result for the current house.

Instead of using an array to store the maximum amount for each house, we can use two variables to keep track of the maximum amount we can rob up to the previous two houses.

Let's define:

  • prev1: Maximum amount of money we can rob up to the previous house.
  • prev2: Maximum amount of money we can rob up to the house before the previous one.

For each house, we calculate the maximum amount as max(prev2 + nums[i], prev1), and then update prev2 and prev1 for the next iteration.

Algorithm:

  1. Initialize prev1 = 0 and prev2 = 0, representing the maximum amount of money we can rob up to the previous house and the house before the previous one, respectively.
  2. Iterate through the array:
  3. a. Calculate current = max(prev2 + nums[i], prev1).
  4. b. Update prev2 = prev1 and prev1 = current for the next iteration.
  5. Return prev1 as the maximum amount of money we can rob.

Time Complexity:

O(n)

Where n is the number of houses. We iterate through the array once, performing constant-time operations at each step.

Space Complexity:

O(1)

We only use a constant amount of extra space regardless of the input size.

Approach 3: Recursive Approach with Memoization

We can also solve this problem using a recursive approach with memoization. The idea is to define a recursive function that calculates the maximum amount of money we can rob starting from a given house.

Let's define rob(i) as the maximum amount of money we can rob starting from the i-th house. We have two options:

  1. Rob the current house: rob(i) = nums[i] + rob(i+2)
  2. Skip the current house: rob(i) = rob(i+1)

We choose the option that gives us the maximum amount: rob(i) = max(nums[i] + rob(i+2), rob(i+1)).

To avoid redundant calculations, we use memoization to store the results of subproblems.

Algorithm:

  1. Define a recursive function rob(i) that calculates the maximum amount of money we can rob starting from the i-th house.
  2. Use memoization to store the results of subproblems.
  3. For each house, calculate rob(i) = max(nums[i] + rob(i+2), rob(i+1)).
  4. The base cases are: rob(n) = 0 and rob(n-1) = nums[n-1].
  5. Return rob(0) as the maximum amount of money we can rob.

Time Complexity:

O(n)

Where n is the number of houses. With memoization, each subproblem is computed only once, and there are n subproblems.

Space Complexity:

O(n)

We use an array of size n to store the results of subproblems, plus the recursion stack which can go up to O(n) in the worst case.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function rob(nums):
    n = length of nums
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
 
    dp = new array of size n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
 
    for i from 2 to n-1:
        dp[i] = max(dp[i-2] + nums[i], dp[i-1])
 
    return dp[n-1]
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone