House Robber — Java Coding Problem
Difficulty: medium | Category: dynamic-programming
Problem Description
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money. You cannot rob two adjacent houses (the alarm will trigger). Given an integer array `nums` representing each house's money, return the maximum amount you can rob. Hint: DP — at each house you either rob it (plus best from 2 before) or skip it (best from previous house). `dp[i] = max(dp[i-1], dp[i-2] + nums[i])`.
Examples
Example 1
Input: nums = [1, 2, 3, 1]
Output: 4
Explanation: Rob house 1 (1) + house 3 (3) = 4.
Example 2
Input: nums = [2, 7, 9, 3, 1]
Output: 12
Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12.