“This is the 18th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Topic describes

You are a professional thief, planning to rob the houses along the street. There is a certain amount of cash hidden in each room, and the only constraint on your ability to steal is that adjoining houses are equipped with interconnected security systems that will automatically alert the police if two houses are broken into on the same night.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount of money you can steal in one night without setting off the alarm.

  • Example 1:

Input:,2,3,1 [1]

Output: 4

Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.

  • Example 2:

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

Output: 12

Explanation: Stealing House no. 1 (amount = 2), House No. 3 (amount = 9), then House No. 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.

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

Subject analysis

If there is only one house, the thief has no choice but to steal the maximum amount by stealing the house. If there are two rooms, they must be next to each other, so you can only steal the room with the higher amount.

First, exclude the case that the array length is less than 3. According to dynamic programming, assign the value of each element of the array to the maximum value of the current position strategy

Since neighboring houses cannot be robbed, then the NTH room cannot be robbed after the n+1 room is robbed, so the maximum amount of dp[n+1] that can be stolen from the first N +1 room must be the larger value of the following two:

  1. Don’t grab the firstn+1 room, thus equal to the maximum amount of the first n houses, i.e. Dp [n+1] = dp[n];
  2. Rob the n+1 room, can’t rob the n room; Dp [n+1] = dp[n-1] + num;

Select the option with the greater total amount of theft from the two options. The total amount of theft corresponding to this option is the maximum total amount of theft for the first K houses.

Finally, the transfer equation: dp[n+1] = Max (dp[n], DP [n-1]+num)

Time complexity: Time complexity: O(n), where n is the array length.

Space complexity: O(1).

class Solution { public int rob(int[] nums) { int max = 0, n = nums.length; if (n == 1) { return nums[0]; } else if (n == 2) { return Math.max(nums[0], nums[1]); } nums[1] = Math.max(nums[0], nums[1]); for (int i=2; i<n; i++) { nums[i] = Math.max(nums[i-2] + nums[i], nums[i-1]); if (nums[i] > max) { max = nums[i]; } } return max; }}Copy the code