This is the 18th day of my participation in the August Genwen Challenge.More challenges in August

Robbery (Question No. 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:4Explanation: Stealing1House no. (Amount =1) and steal3House no. (Amount =3). Maximum amount stolen =1 + 3 = 4 ใ€‚
Copy the code

Example 2:

Input:2.7.9.3.1] output:12Explanation: Stealing1House no. (Amount =2), and steal3House no. (Amount =9) and steal5House no. (Amount =1). Maximum amount stolen =2 + 9 + 1 = 12 ใ€‚
Copy the code

Tip:

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

link

Leetcode-cn.com/problems/ho…

explain

This one, this is a classic DP.

Let’s take a look at the problem, the problem is simplified: you’re given an array, you can’t take adjacent elements, you can take the largest number.

The idea of DP is very simple, to have a DP array to record the maximum value that can be taken on each element. So dp[I] is the largest number in the current position.

So how do I find dp[I]? Dp [I] actually has two possibilities:

  • Instead of taking the first digit, take the first two digits, and add the current digit, which is thetadp[i - 2] + nums[i]
  • If you take the first number, you can’t take the current element, which is thetad[i - 1]

So the formula DP is:

dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
Copy the code

Take the maximum of both, and the last element of the DP array is the maximum that you can take in the entire array.

Let’s think again. According to the DP formula of ๐Ÿ‘†, it can be found that the sum of the first two elements of DP [I] is the same, so we can use only two variables to store the first two values instead of an array. Update these two variables every time, and then we can get the final result.

And the space complexity went from O(n) to O(1), which is optimized a little bit.

Your own Answer (DP)

Classic DP operates as explained ๐Ÿ‘‡ :

var rob = function(nums) {
  const dp = new Array(nums.length)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])}return dp[nums.length - 1]};Copy the code

Note the initial assignment of dp[0] and dp[1], since dp[I] is related to the first two digits, the first two values must be initialized before the loop starts, otherwise the first two values may not be taken.

And then the loop just keeps updating the DP array, and so on, the last element of the DP array is the value that we need to return.

Your own answer (DP+ Dimension reduction)

As explained, it is perfectly possible to replace arrays with two variables ๐Ÿ‘‡ :

var rob = function(nums) {
  let before1 = Math.max(nums[0], nums[1) | |Number.MIN_SAFE_INTEGER
  let before2 = nums[0]
  for (let i = 2; i < nums.length; i++) {
    [before1, before2] = [Math.max(before2 + nums[i], before1), before1]
  }
  return Math.max(before1, before2)
};
Copy the code

Replace the previous two variables with before1 and replace the previous two variables with before2. Keep updating before1 and before2 throughout the loop.

Another thing to note is the assignment of before1, because if the array is of length 1, the value picked up by before1 is NaN.

Can you believe that math. Max (NaN, 0) is NaN? This will return NaN, which is awkward, so use number.min_safe_INTEGER to represent the nonexistent before1, or -infinity, optionally.

The final return value must also be evaluated in before1 and before2, because if the array has length 2 and the second element is larger than the first, before2 is the answer, and if the array has length 1, before1 is the answer, so take the larger of the two.

ideas

In fact, I found an interesting answer:

The guy who wrote this answer is really cute ~





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)