This is the 19th day of my participation in the August Wenwen Challenge.More challenges in August

Robbery II (Item No. 213)

The title

You are a professional thief, planning to rob the houses along the street, each with a certain amount of cash hidden inside. All the houses in this place are in a circle, which means that the first house and the last house are next to each other. At the same time, adjacent houses are equipped with an interconnected anti-theft system, which will automatically alarm if two adjacent houses are broken into by thieves on the same night.

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

Example 1:

Enter: nums = [2.3.2] output:3Explanation: You can't steal first1House no. (Amount =2) and steal3House no. (Amount =2), because they are adjacent.Copy the code

Example 2:

Enter: nums = [1.2.3.1] output:4Explanation: You can steal first1House no. (Amount =1) and steal3House no. (Amount =3). Maximum amount stolen =1 + 3 = 4 。
Copy the code

Example 3:

Enter: nums = [0] output:0
Copy the code

Tip:

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

link

Leetcode-cn.com/problems/ho…

explain

This one. This one’s a double.

The first house is connected to the last house, so if you choose the first house, you cannot choose the last one, and if you choose the last one, you cannot choose the first one.

In the author’s opinion, it is mainly necessary to distinguish whether the first one is selected or not, and the other ones should be consistent with the first one.

So if you want to use DP for this problem, you have to evolve from a one-dimensional array in problem 1 to a two-dimensional array, where the first row of the array represents the second house that was selected, and the second row represents the first house that was selected.

After that, the loop updates the DP two-dimensional array, but there are two special cases that need to be noted:

  • Initialize the assignment phase

    • If it’s the first row, that means the first house is not selected, sodp[0][0]That’s 0, and the second element is the second element, but the second element might not exist, because the minimum length of the array is 1, so if it doesn’t exist, you need to putdp[1][1]The assignment forNumber.MAX_SAFE_INTEGER.
    • If it’s the second row, the first house is selected, thendp[1][0]I need to select the first element,dp[1][1]You need to select the maximum value of the first two elements, but the second element may not exist, in which case, the value taken isNaNAnd I’m going to have the same problem that I had in the first questionNaN, then you need to assign to the second element if it does not existNumber.MAX_SAFE_INTEGERSame as the first case.

  • Iterative phase

    Here, too, you need to discriminate based on whether the first element is selected or not.

    Integral iteration method is the same, according to the first two elements to infer the current position of the maximum, to this point, and one of the world, is not much, the key is to select the first element is the case, if the selected the first case, then a place at the end of the iteration, can no longer iterations, because can’t choose the last element, Therefore, the result of the previous iteration should be assigned to the current position.

After solving these two problems, there is no difficulty left. The overall logic is the same as in the previous question, and details need to be dealt with.

Your own answer (DP+ array)

That’s the answer in the explanation, Easy.

var rob = function(nums) {
  const len = nums.length
  const dp = Array.from({length: 2}, () = > new Array(len))
  dp[0] [0] = 0
  dp[0] [1] = nums[1] | |Number.MIN_SAFE_INTEGER
  dp[1] [0] = nums[0]
  dp[1] [1] = Math.max(nums[1] | |Number.MIN_SAFE_INTEGER, nums[0])
  for (let i = 2; i < len; i++) {
    if(i ! == len -1) {
      dp[1][i] = Math.max(dp[1][i - 2] + nums[i], dp[1][i - 1])}else {
      dp[1][i] = dp[1][i - 1]
    }
    dp[0][i] = Math.max(dp[0][i - 2] + nums[i], dp[0][i - 1])}return Math.max(dp[0][len - 1], dp[1][len - 1])}Copy the code

After changing the DP array from one-dimensional to two-dimensional, there are naturally more elements to initialize and assign, and the code looks a little disgusting and the logic a little hard to understand, but otherwise it’s fine.

Your own answer (DP+ Dimension reduction)

Dimension reduction here is also very similar to the previous problem, but it needs to upgrade from two variables in the previous problem to four variables. It needs to pay attention to the same solution as 👆, initialization assignment problem, and the problem of selecting the last iteration value of the first element.

var rob = function(nums) {
  const len = nums.length
  let before00 = 0
  let before01 = nums[1] | |Number.MIN_SAFE_INTEGER
  let before10 = nums[0]
  let before11 = Math.max(nums[1] | |Number.MIN_SAFE_INTEGER, nums[0])
  for (let i = 2; i < len; i++) {
    if(i ! == len -1) {
      [before10, before11] = [before11, Math.max(before10 + nums[i], before11)]
    }
    [before00, before01] = [before01, Math.max(before00 + nums[i], before01)]
  }
  return Math.max(before01, before11)
}
Copy the code

The code looks simpler than the two-dimensional array scheme, but the logic is not fundamentally different, simply because the variables remove some special case judgments.

A better way (DP+ Grouping)

In fact, about this problem, can we break it down into two first questions?

  • If the first house is available

    Is the difference between going from the first element of the array to the second-to-last element of the array?

  • If the first house is not available

    Is the interval of the problem going from the second element of the array to the reciprocal first element of the array?

After knowing these two questions, the answer actually comes out, as long as you write a tool method, used to calculate the maximum value of a certain interval, respectively for these two intervals, compare the results of the two, choose the maximum, then this problem is not solved?

Although this method sweeps the array twice, it is much better at understanding than the straightforward solution. There is no complex judgment logic for multiple cases because different cases are grouped at the beginning.

var rob = function(nums) {
  const length = nums.length;
  if (length === 1) {
    return nums[0];
  } else if (length === 2) {
    return Math.max(nums[0], nums[1]);
  }
  return Math.max(robRange(nums, 0, length - 2), robRange(nums, 1, length - 1));
};

const robRange = (nums, start, end) = > {
  let first = nums[start], second = Math.max(nums[start], nums[start + 1]);
  for (let i = start + 2; i <= end; i++) {
    const temp = second;
    second = Math.max(first + nums[i], second);
    first = temp;
  }
  return second;
}
Copy the code





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)