House Robber

Medium

dynamic-programming

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. The only constraint stopping you from robbing each of them is that adjacent houses have security systems connected - it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Recurrence Relation: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

At each house, you decide: skip it (take previous max) or rob it (take value + max from two houses back).

Example 1

Input: nums = [1,2,3,1]

Output: 4

Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total = 1 + 3 = 4.

Example 2

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total = 2 + 9 + 1 = 12.

Example 3

Input: nums = [2,1,1,2]

Output: 4

Explanation: Rob house 1 (money = 2) and house 4 (money = 2). Total = 4.

Constraints

•1 <= nums.length <= 100
•0 <= nums[i] <= 400

Show Hints (4)

Hint 1: For each house, you have two choices: rob it or skip it.

Hint 2: If you rob house i, you cannot rob house i-1. Your total is nums[i] + best from houses 0 to i-2.

Hint 3: If you skip house i, your total is the best from houses 0 to i-1.

Hint 4: The answer is the maximum of these two choices.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?