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 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 tonight without setting off the alarm.

Example 1:

Input: nums = [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: nums = [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

Example 3:

Input: nums = [0] Output: 0Copy the code

Tip:

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

Divide and conquer approach

In 198. Robbery – From Divide and Conquer to Dynamic Programming, the paper analyzes how to steal 0 ~ N houses without stealing the maximum amount of two houses in a row. The last house is connected to the first house. So the first room and the last can’t be stolen at the same time. This condition can be decomposed: the maximum amount of money for stealing the 1st ~ n-1 and the 2nd ~ N houses can be calculated respectively, and the one with the larger value is the maximum amount of money for stealing the 1st ~ N houses.

Break into a house and rob a house

In 198. Plunder – from divide and conquer to dynamic programming, the solution idea is to calculate the difference between stealing and not stealing the I to define the state. At the end of the last article, it was revealed that another state can be used to solve the problem, which is used here The maximum amount of money a house can get as a state, so as long as the one-dimensional state, the implementation is more concise.

function rob(nums: number[]) :number {
  const dp: number[] = []
  for (let i = 0; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 1]????0, (dp[i - 2]????0) + nums[i])
  }
  return dp[nums.length - 1]}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

213. Looting – II

According to the previous ideas, find the maximum amount of 1 ~ n-1 and 2 ~ n respectively, and then take the larger one.

Dp1 indicates the state of stealing 1 to N-1 houses, and Dp2 indicates the state of stealing 2 to N houses

Note that there is a special boundary to deal with here. When there is only one house, the maximum amount you can steal is the only house you can steal.

In addition, for indexes less than 0, use?? (null value merge operator) to deal with 0, such as stealing the first house, when I -1 and I -2 do not exist, which is equivalent to stealing 0 dollars.

Of course, there are other ways to do this, such as adding two zeros before nums, or extra checks to see if I -1 and I -2 are less than zero, or offsetting the dp array by two digits. It’s just that I personally feel direct use of?? It’s a little bit more concise.

function rob(nums: number[]) :number {
  const n = nums.length
  if (n === 1) return nums[0]

  const dp1: number[] = []
  for (let i = 0; i < n - 1; i++) {
    dp1[i] = Math.max(dp1[i - 1]????0, (dp1[i - 2]????0) + nums[i])
  }

  const dp2: number[] = []
  for (let i = 1; i < n; i++) {
    dp2[i] = Math.max(dp2[i - 1]????0, (dp2[i - 2]????0) + nums[i])
  }

  return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1])}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Optimize the code

We can write both loops into one loop, so we don’t have to do one loop, so it looks a lot cleaner

A small processing here is to directly initialize DP1 [0] to NUMs [0] and dp2[0] to 0, which dispenses with the judgment that there is only one house. So we can iterate directly from the second house, which in the array is index I, which starts at 1.

function rob(nums: number[]) :number {
  const n = nums.length
  const dp1: number[] = [nums[0]]
  const dp2: number[] = [0]

  for (let i = 1; i < n; i++) {
    if (i < n - 1) dp1[i] = Math.max(dp1[i - 1], (dp1[i - 2]????0) + nums[i])
    dp2[i] = Math.max(dp2[i - 1], (dp2[i - 2]????0) + nums[i])
  }

  return Math.max(dp1[dp1.length - 1], dp2[dp2.length - 1])}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The compression state

We find that DP1 [I] is only related to DP1 [i-1] and DP1 [i-2]. At this time, two variables can be used to replace dp array for state compression, and the same is true for DP2

function rob(nums: number[]) :number {
  const n = nums.length
  let [cur1, pre1] = [nums[0].0]
  let [cur2, pre2] = [0.0]

  for (let i = 1; i < n; i++) {
    if (i < n - 1) [cur1, pre1] = [Math.max(cur1, pre1 + nums[i]), cur1] ; [cur2, pre2] = [Math.max(cur2, pre2 + nums[i]), cur2]
  }

  return Math.max(cur1, cur2)
}
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

Robbery series:

  • 198. Robbery
  • # 213. Robbery – II