213. A house raid II

Answer:

  1. On the basis of 213. Raiding II, this topic connects the houses at the beginning and the end together, thus producing two scenes:

    • If you steal the first house, you can’t steal the last house, it’s the same as stealing from the first house to the last house.
    • If you steal the last house, you can’t steal the first house, it’s the same as stealing from the second house to the last house.

    So we can divide the house into two sections and then maximize the results together.

  2. Analysis of state transition equation:

    • For house I, there are two scenarios, steal or not steal:

      • If I don’t steal it,dp[i] = dp[i - 1] + 0
      • If stolen, then all the possible situation, before I wasdp[i] = Math.max(nums[i] + dp[i - 2], nums[i] + dp[i - 3], ...). So we know that each of these digits is taking the maximum possible value. So we can derive thisdp[i - 2] > dp[i - 3] > dp[i - 4]..., sodp[i - 2]The rest of the comparison can be omitted.

    • State transition equation: dp[I] = math.max (dp[I] + 0, NUMs [I] + dp[I]).

/ * * *@param {number[]} nums
 * @return {number}* /
var rob = function (nums) {
  // Steal from 0 to nums.length-2 with dp1 recursion
  // Since we are recursing two levels forward, two elements are created at one initialization, and both are maximized
  let dp1 = [
    // select * from user where id = 0
    nums[0] | |0.// Only one of the first and the first households can be stolen
    Math.max(nums[0] | |0, nums[1] | |0)];// Recurse from 1 to nums.length-2
  for (let i = 2; i < nums.length - 1; i++) {
    dp1[i] = Math.max(
      // If you don't steal i-1, you only need to consider i-1
      dp1[i - 1].// If you steal I, you need to consider i-2 to 0, and i-2 must be greater than all of the previous results
      dp1[i - 2] + nums[i],
    );
  }

  // Use dp2 recursion to steal from 1 to nums.length-1
  // Since we are recursing two levels forward, two elements are created at one initialization, and both are maximized
  Dp2 [0] stores 0 placeholders to ensure a one-to-one correspondence between dp2 index and NUMS
  let dp2 = [
    0.// I stole the first house
    nums[1] | |0.// Only one of the first and second households can be stolen
    Math.max(nums[1] | |0, nums[2] | |0)];// Recurse from 0 to nums.length-1
  for (let i = 3; i < nums.length; i++) {
    dp2[i] = Math.max(
      // If you don't steal i-1, you only need to consider i-1
      dp2[i - 1].// If you steal I, you need to consider i-2 to 0, and i-2 must be greater than all of the previous results
      dp2[i - 2] + nums[i],
    );
  }

  return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1]);
};
Copy the code