198. House Robber

medium dynamic-programming

Maximize the amount you can rob without robbing adjacent houses.

Given an integer array nums representing money at each house, return the maximum amount you can rob without robbing two adjacent houses.

Approach

DP: at each house, choose to rob it (dp[i-2] + nums[i]) or skip it (dp[i-1]) — O(n) time, O(1) space.

Solutions

Ruby

def rob(nums)
  return 0 if nums.empty?
  return nums[0] if nums.length == 1
  a, b = nums[0], [nums[0], nums[1]].max
  (2...nums.length).each do |i|
    a, b = b, [b, a + nums[i]].max
  end
  b
end

Python

def rob(nums: list[int]) -> int:
    if not nums: return 0
    if len(nums) == 1: return nums[0]
    a, b = nums[0], max(nums[0], nums[1])
    for i in range(2, len(nums)):
        a, b = b, max(b, a + nums[i])
    return b

Go

func rob(nums []int) int {
    if len(nums) == 0 { return 0 }
    if len(nums) == 1 { return nums[0] }
    a, b := nums[0], max(nums[0], nums[1])
    for i := 2; i < len(nums); i++ {
        a, b = b, max(b, a+nums[i])
    }
    return b
}

func max(a, b int) int {
    if a > b { return a }
    return b
}

TypeScript

function rob(nums: number[]): number {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];
    let a = nums[0], b = Math.max(nums[0], nums[1]);
    for (let i = 2; i < nums.length; i++) {
        [a, b] = [b, Math.max(b, a + nums[i])];
    }
    return b;
}

Elixir

defmodule Solution do
  def rob([]), do: 0
  def rob([h]), do: h
  def rob([a, b | rest]), do: do_rob(rest, a, max(a, b))

  defp do_rob([], _a, b), do: b
  defp do_rob([h | t], a, b), do: do_rob(t, b, max(b, a + h))
end