noodleProblems/
House Robber
#153

House Robber

AlgorithmmediumArrayDynamic Programming

You are planning to rob houses arranged in a single line. nums[i] is the amount of money stashed in house i.

Every house is wired to a shared security system: robbing two houses that are directly adjacent (indices i and i + 1) on the same night trips the alarm. Given nums, return the maximum total amount you can rob without robbing two adjacent houses.

Example cases

  • skip the middle house
    in nums = [1,2,3,1]
    out 4
    Rob houses 0 and 2: 1 + 3 = 4.
  • rob every other house
    in nums = [2,7,9,3,1]
    out 12
    Rob houses 0, 2, and 4: 2 + 9 + 1 = 12.
  • endpoints beat the middle pair
    in nums = [2,1,1,2]
    out 4
    Rob houses 0 and 3: 2 + 2 = 4.

Constraints

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
Saved
nums =
[1,2,3,1]