House Robber

You are a professional robber planning to rob houses along a street. Each house contains a certain amount of money, but adjacent houses have connected security systems that automatically alert the police if two adjacent houses are robbed on the same night.

Given an array nums where nums[i] represents the money in the $i$-th house, return the maximum amount of money you can rob without triggering the alarm.

Examples

Example 1:

• Input: nums = [1, 2, 3, 1]
• Output: 4
• Explanation: Rob house 0 ($1)andhouse2($3) for a total of $4

Example 2:

• Input: nums = [2, 7, 9, 3, 1]
• Output: 12
• Explanation: Rob house 0 ($2),house2($9), and house 4 ($1)foratotalof$12

Dynamic Programming Solution

This is a classic dynamic programming problem, similar to Climbing Stairs. At each house $i$, the robber faces a choice:

1. Rob house $i$: Take nums[i] plus the maximum from houses up to $i-2$
2. Skip house $i$: Keep the maximum from houses up to $i-1$

The recurrence relation: $best[i]=\max (best[i-1],best[i-2]+nums[i])$

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

The base cases of n=1 and n=2 are predefined.

#include <vector>
using namespace std;
 
class Solution {
public:
  int rob(vector<int> &nums) {
      if (nums.size() == 1)
          return nums[0];
      if (nums.size() == 2)
          return (nums[0]>nums[1]) ? nums[0] : nums[1];
      vector<int> bestUntil(nums.size(),0);
      bestUntil[0] = nums[0];
      bestUntil[1] = (nums[0]>nums[1]) ? nums[0] : nums[1];
      for(int i = 2; i<nums.size(); i++) {
          bestUntil[i] = max(bestUntil[i-1],bestUntil[i-2]+nums[i]);
      }
      return bestUntil[nums.size()-1];
  }
};