This article explains the solution of 198

The title

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

Solution 1: Divide and conquer

Get the maximum amount of money to steal 0~ I houses, and do not steal two houses in a row

For the i-th room, you can choose to steal or not steal, breaking it down into two cases:

  1. Maximum amount of money you can get for stealing house IF (I, stealing)
  2. Maximum amount of money you can get for not stealing house IF (I, don't steal)

Take the larger of them, that is, the maximum amount of stolen 0~ I houses

In the first case, since we can’t steal the i-1 house because we stole the i-1 house, the maximum amount of money we can get for not stealing the i-1 house plus the amount we can get for stealing the i-1 house is f(I, stolen) = F (i-1, not stolen) + nums[I].

For the second case, if we don’t steal the ith house, there’s no limit on the i-1 house, and the maximum amount of money we can get in this case is the larger of the two cases,f(I, no steal) = Max (f(i-1, no steal))

And so on, until I is 0.

Use flag to indicate whether to steal house I

function rob(nums: number[]) :number {
  const n = nums.length
  const helper = (i: number.flag: boolean) :number= > {
    if (i === 0) return flag ? nums[i] : 0

    // To steal this house, you have to not steal the i-1 house
    if (flag) return helper(i - 1.false) + nums[i]
    // If you don't steal this house, you never steal the i-1 house and the larger of the i-1 houses is the maximum that can be stolen up to this room
    else return Math.max(helper(i - 1.false), helper(i - 1.true))}return Math.max(helper(n - 1.false), helper(n - 1.true))}Copy the code
  • Time complexity: O(2n)O(2^n)O(2n)
  • Space complexity: O(n)O(n)O(n)

Time complexity: This time complexity is not easy to derive, but you can use an array to count the number of times each layer is accessed. The result is a Pebonacci sequence, and the total time complexity is exponential.

| | 0 I (don't steal) 1 (steal) | | | -- - | -- -- -- -- -- - | -- - | | 1 | 10946 | 6765 | | | 6765 | 4181 | 2 | 3 | 4181 | 2584 | | 2584 | | 4 | 1597 | | 1597 | | 987 | | 987 | | 610 | | 610 | | 377 | | 377 | 233 8 | | 9 | 233 | | 144 | | 144 | 89 | | 11 55 | | 89 | | 12 55 34 | | | | | 34 13 | | 21 13 14, 21 | | | | | | 13 15 8 | | | | | | 5 8 16 17 | | | | 3 | | 3 19 | 2 | 1 | 2 | | | | | 1 | 1 20 |Copy the code

Space complexity: O(n)O(n)O(n) O(n) if the recursive stack is counted, O(1)O(1)O(1) if the recursive stack is not counted

Optimization time: Memorized search

In the above solution, there are a lot of repeated calculations, and the time complexity is horrible and exponential, which we can optimize by adding caching.

For convenience,flag is represented by 0 or 1, where 0 indicates no stealing and 1 indicates stealing

function rob(nums: number[]) :number {
  const n = nums.length
  const cache: number[] [] =new Array(n).fill(0).map(() = > [0.0])
  const helper = (i: number.flag: 0 | 1) :number= > {
    if (i === 0) return flag ? nums[i] : 0
    if (cache[i][flag]) return cache[i][flag]

    cache[i][flag] = flag
      ? helper(i - 1.0) + nums[i]
      : Math.max(helper(i - 1.0), helper(i - 1.1))

    return cache[i][flag]
  }

  return Math.max(helper(n - 1.0), helper(n - 1.1))}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Time complexity: after optimization, each house will only be accessed twice, so the time complexity is O(2n)O(2n)O(2n), generally omits the preceding constant, and is directly expressed as O(n)O(n)O(n) O(n)

Space complexity: The cache uses O(n)O(n)O(n) space

From the bottom up

function rob(nums: number[]) :number {
  const n = nums.length
  const helper = (i = 0.sum: [number.number] = [0.0) :number= > {
    if (i === nums.length) return Math.max(... sum)return helper(i + 1[Math.max(... sum), sum[0] + nums[i]])
  }

  return helper()
}
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Dynamic programming

You can use the cache in the mnemonized search above directly as the state of dynamic programming

  • dp[i]: the maximum amount that can be stolen between I, wheredp[i][0]Represents the maximum amount that can be stolen between I without stealing,dp[i][1]Represents the maximum amount that can be stolen between I
  • Recursive formula:
    • dp[i][0]=max(dp[i-1][0],dp[i-1][1])
    • dp[i][1]=dp[i-1][0]+nums[i]
  • Boundary:
    • dp[0]=[0,nums[0]]
function rob(nums: number[]) :number {
  const n = nums.length
  const dp: number[] [] =new Array(n).fill(0).map(() = > [])
  dp[0] = [0, nums[0]]
  for (let i = 1; i < nums.length; i++) {
    dp[i] = [Math.max(... dp[i -1]), dp[i - 1] [0] + nums[i]]
  }

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

Space optimization

You can see that the i-th state is only related to the i-1st state, so you can compress the state, using two variables instead of the DP array to store the state

function rob(nums: number[]) :number {
  let [num1, num2] = [0, nums[0]]
  for (let i = 1; i < nums.length; i++) { ; [num1, num2] = [Math.max(num1, num2), num1 + nums[i]]
  }

  return Math.max(num1, num2)
}
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Dp [I]= Max (dp[i-1],dp[i-2]+nums[I])

Robbery series:

  • 198. Robbery
  • # 213. Robbery – II