The original problem

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 security system, if two adjacent houses are broken into on 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 without setting off the alarm.

Example 1:

Input: [2,3,2] Output: 3 Explanation: You cannot steal House 1 (amount = 2) and then house 3 (amount = 2) because they are adjacent.Copy the code

Example 2:

Input: [1,2,3,1] Output: 4 Explanation: You can steal House # 1 first (amount = 1) and then House # 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4.Copy the code

Train of thought

198. What is the meaning of the passage? Due to the limitation of the topic, it should be noted that the first and last house can not be robbed at the same time

I won’t go over the derivation of the state transition equation here, but if you don’t understand it, you can see the solution on problem 198.

When I was thinking about 🤔, I fell into the trap of thinking,

Maximum amount = Max (maximum amount - the first amount, maximum amount - the last amount) if the maximum amount includes the first and the last

I wasted an hour of my time doing this. In the process of trial and error, the wrong direction of thinking was discovered. Here is a counter example


const nums = [2.2.4.3.2.5]

// The maximum value is 11, but the end is looped
const max = 2 + 4 + 5

// Max - 2 === 9 or Max - 5 == 6 are not maximum values
// In the case of avoiding loops, the maximum value
const max = 2 + 3 + 5
Copy the code

Through this counter example, we can see that we can not simply and rudely remove the tail, we need to recalculate the optimal numS solution when we remove the tail or head.

code


/** * @param {number[]} nums * @return {number} */
var rob = function (nums) {

  if (nums.length === 0) {
    return 0
  }

  if (nums.length === 1) {
    return nums[0]}const getDp = (nums) = > {
    const dp = []
    for (let i = 0; i < nums.length; i++) {
      let m = dp[i - 2= = =undefined ? 0 : dp[i - 2]
      m = m + nums[i]
      let n = dp[i - 1= = =undefined ? 0 : dp[i - 1]
      if (m > n) {
        dp[i] = m
      } else {
        dp[i] = n
      }
    }
    return dp
  }


  const nums1 = [...nums]
  nums1.shift()
  const nums2 = [...nums]
  nums2.pop()
  // The best result after removing the head
  const dp1 = getDp(nums1)
  // Best result after tail removal
  const dp2 = getDp(nums2)
  return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1])};Copy the code