#198 - House Robber

MediumDP - 1D

Given an array nums representing the amount of money in each house, you cannot rob two adjacent houses. Return the maximum amount you can rob.

Input	Output
nums = [1,2,3,1]	4
nums = [2,7,9,3,1]	12

Solution Space

Try it

/**
 * Returns the maximum amount robbed from non-adjacent houses.
 *
 * @param nums Amount of money in each house
 * @returns Maximum robbery profit
 */
export function rob(nums: number[]): number {
  let prev2 = 0; // max profit excluding the last house
  let prev1 = 0; // max profit including/excluding the last house

  for (const num of nums) {
    const curr = Math.max(prev1, prev2 + num);
    prev2 = prev1;
    prev1 = curr;
  }

  return prev1;
}

Approach: bottom-up DP – at each house, choose max of (skip this house = `prev1`) or (rob this house = `prev2 + nums[i]`). Two variables suffice since each state depends only on the previous two.

Time: O(n) – single pass.

Space: O(1) – two rolling variables.

#139 Word Break

#746 Min Cost Climbing Stairs