v9.1.1
Menu

House Robber

mediumPRODynamic ProgrammingNetflix DSA

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

Example

Input
1,2,3,1
Output
4
Reasoning
  • The input 1,2,3,1 lists the cash in four houses on a street, left to right: 1,2,3,11, 2, 3, 1. The output is the largest total you can collect.
  • The only rule: no two neighbouring houses may both be chosen. So houses 1 and 2, 2 and 3, or 3 and 4 never appear together.
  • With four houses, the allowed picks of two or more are {1,3}\{1,3\}, {1,4}\{1,4\} and {2,4}\{2,4\}. Three houses are impossible, since any three of four contain a neighbouring pair.
  • Their totals: {1,3}→1+3=4\{1,3\} \to 1 + 3 = 4, {1,4}→1+1=2\{1,4\} \to 1 + 1 = 2, {2,4}→2+1=3\{2,4\} \to 2 + 1 = 3. A single house gives at most 33.
  • The best is 44, from houses 1 and 3. Notice that taking the richest house (house 3) rules out both its neighbours, but house 1 is still free to add on.

Constraints

  • 1 <= len(nums) <= 100
  • 0 <= nums[i] <= 400

More from Netflix DSA

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Test results

Sign in to run your code against the test cases.