House Robber II

Summary

The House Robber II problem is a classic dynamic programming problem that involves maximizing the loot collected from a series of houses. The twist here is that we can't rob two adjacent houses, and our goal is to maximize the total loot collected while following this constraint.

Detailed Explanation

Given an array nums representing the amount of loot available at each house, our task is to find the maximum loot that can be collected without robbing two adjacent houses. We'll use dynamic programming to solve this problem.

Here's a step-by-step breakdown of the solution:

1. Initialize a variable dp with length n, where n is the number of houses.
2. Set dp[0] = nums[0], since we can collect loot from the first house.
3. For each house starting from the second (index 1), calculate the maximum loot that can be collected by considering two options:
   • Rob the current house and skip the previous one (dp[i-2] + nums[i]).
   • Don't rob the current house and collect loot from the previous one (dp[i-1]).
4. Update dp[i] with the maximum value between these two options.
5. The maximum loot that can be collected is stored in dp[n-1].

Time complexity: O(n) Space complexity: O(1), since we only need a constant amount of space to store the dynamic programming table.

Here's an ASCII art diagram illustrating the problem:

  +-----+-----+-----+-----+
  | 0   | 1   | 2   | ... |
  +-----+-----+-----+-----+
       |         |
       |  Rob/Don't  |
       |  Rob Next  |
  +-----+-----+-----+-----+

Optimized Solutions

Java