MEDIUM NC#101 Blind #22 Dynamic Programming 1D

198. House Robber

📖 Problem

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. You cannot rob two adjacent houses.

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Array DP table updates
  • •State transition thinking
  • •Base case initialization

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Dynamic Programming reasoning pattern
  • •Apply Recursion reasoning pattern

💡 Approach

  • → dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • → Use two variables to track previous two states for O(1) space
  • → At each house, decide: rob current + skip previous, or skip current
  • → Time: O(n), Space: O(1)

🧭 Prerequisites

#139 Word Break #152 Maximum Product Subarray

🛠️ Hints & Pitfalls

Hints

  • •dp[i] = max(dp[i-1], dp[i-2] + nums[i])
  • •Use two variables to track previous two states for O(1) space
  • •At each house, decide: rob current + skip previous, or skip current

Common Pitfalls

  • •Time: O(n), Space: O(1)

🧪 Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
rob([1,2,3,1]);
Expected:
4
Test Case 2
Not run
Input:
rob([2,7,9,3,1]);
Expected:
12
Test Case 3
Not run
Input:
rob([]);
Expected:
0

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#91 Decode Ways #139 Word Break #152 Maximum Product Subarray #213 House Robber II #300 Longest Increasing Subsequence
⌘K Search ⌘↩ Run ⌘S Submit