198. Robbery

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: [1,2,3,1] Output: 4 Explanation: Steal House # 1 (amount = 1), then steal House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.Copy the code

Example 2:

Input: [2,7,9,3,1] Output: 12 Explanation: Steal House 1 (amount = 2), House 3 (amount = 9), then House 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code

Tip:

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

code

/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function (nums) {
  const { length } = nums;
  if (length == 0) return 0;
  if (length == 1) return nums[0];
  if (length == 2) return Math.max(nums[0], nums[1]);
  let prev = nums[0], cur = Math.max(nums[0], nums[1]);
  for (let i = 2; i < length; i++) {
    const max = Math.max(prev + nums[i], cur);
    prev = cur;
    cur = max;
  }
  return cur;
};
Copy the code

Answer ideas

Let’s start with the simplest case. If there is only one house, the house can be stolen up to the maximum amount. If there are only two houses, because the two houses are adjacent, can not steal at the same time, can only steal one of the houses, so choose the higher amount of the house to steal, you can steal the highest total amount.

If there are more than two houses, how do you calculate the maximum amount of money you can steal? For room k (k>2), there are two options:

  1. If you steal the kK house, you cannot steal the kK houseK - 1Two houses, and the total amount stolen isK - 2The maximum total amount of the house is nokThe sum of the houses.
  2. Don’t steal the firstkTwo houses, and the total amount stolen isK - 1The maximum total amount of a house.

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.

Dp [I] is used to represent the highest total amount that can be stolen from the previous I house, then the following state transition equation can be obtained:

Dp [I] = Max (dp [I] - 2 + nums [I], dp [I - 1))Copy the code

Boundary conditions are as follows:

Dp [0]= NUMs [0] there is only one house, then steal the house DP [1]= Max (nums[0],nums[1]) there are only two houses, select the house with the higher amount to stealCopy the code

The final answer is dp[n−1], where n is the length of the array.