当前位置：网站首页>Brainstorm: Raiders

Brainstorm: Raiders

2022-08-06 23:18:00 【InfoQ】

Topic

You are a professional thief planning to steal houses along the street.There is a certain amount of cash hidden in each room. The only constraint that affects your theft is that the adjacent houses are equipped with interconnected anti-theft systems. If two adjacent houses are broken into by thieves at the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount stored in each house, calculate the maximum amount you can steal overnight without triggering the alarm.

Example 1:

Input: [1,2,3,1]Output: 4 Explanation: Steal house No. 1 (amount = 1), then steal house No. 3 (amount= 3). Maximum amount stolen = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1]Output: 12 Explanation: Stealing House No. 1 (Amount = 2), Stealing House No. 3 (Amount = 9), then steal house 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.

Problem-solving ideas

The problem of robbery is a classic problem solved by dynamic programming.

First step: determine the dp array and the meaning of the subscript, dp[i]: Consider the house within the subscript i (including i), the maximum amount that can be stolen is dp[i].

The second step is to determine the recurrence formula: if the i-th room is stolen, then dp[i] = dp[i - 2] + nums[i], because the i-1th room can no longer be consideredroom, so the maximum amount that can be stolen is dp[i-2] plus the money stolen in the i-th room.

If the i-th room is not stolen, then dp[i] = dp[i - 1].

Then dp[i] takes the maximum value, ie dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

The third step, dp array initialization: From the definition of dp[i], dp[0] must be nums[0], dp[1] is nums[0] and nums[1]The maximum value is: dp[1] = max(nums[0], nums[1]);

The fourth step is to determine the traversal order: dp[i] is based on dp[i- 2] and dp[i - 1] are derived, then it must be traversed from front to back!

Code Implementation

class Solution {
 public int rob(int[] nums) {
 if (nums == null || nums.length ==0) {
 return 0;
 }

 int length = nums.length;
 if(length == 1){
 return nums[0];
 }
 int[] dp = new int[length];
 dp[0] = nums[0];
 dp[1] = Math.max(nums[0], nums[1]);

 for (int i = 2; i < length; i++) {
 dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
 }
 return dp[length - 1];
 }
}