This is the third day of my participation in Gwen Challenge

Problem description

Thieves steal, can not steal two adjacent rooms, or it will trigger the alarm, how to steal the largest amount.

The amount numbers are represented in arrays

[1, 2, 3, 1)Copy the code

Dynamic programming is another basic problem, the first analysis of the problem substructure, and then the formula.

To see if a problem can be solved by dynamic programming, we first see if a problem can be solved by its subproblems.

Here, it is assumed that there are n rooms in total, and the amount of each room is represented by the array nums[] to steal the maximum value of n rooms. Let f(n) be the maximum number of rooms stolen.

  • There are only two ways to steal or not steal the last room

    • Stealing: f (n) = f (n – 2) + nums [n] f (n) = f (n – 2) + nums [n] f (n) = f (n – 2) + nums [n]
    • F (n)= F (n−1) F (n)= F (n-1) F (n)= F (n−1)

  • So the maximum of n rooms is the maximum of stealing or not stealing


    • f ( n ) = m a x ( f ( n – 2 ) + n . f ( n – 1 ) ) f(n) = max(f(n-2) + n, f(n-1))

  • As mentioned above, the problem can be solved by dynamic programming.

let rob = function(nums) {
  let len = nums.length;

  if(len === 0)
  return 0;

  if(len === 1)
  return nums[0];

  if(len === 2)
  return Math.max(nums[0], nums[1]);

  let dp = []; // Use an array to record the maximum number of rooms per k
  dp[0] = 0;
  dp[1] = nums[0];
  dp[2] = Math.max(nums[0], nums[1])
  for(let i = 3; i <= len; i++) {
    dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]); // Use the algorithm just calculated
  }

  return dp[len]; // Return the last value
}
Copy the code

If you look closely, you can see that we only need the maximum values of n-1 and n-2 to get n rooms, so we only need to save the maximum values of the first two cases.

We can figure out the maximum number of n rooms, so we just need to repeat the assignment using a temporary variable, not an array.

So we go from O(N) to O(1).

let rob = function(nums) {
  let len = nums.length;

  if(len === 0)
  return 0;

  if(len === 1)
  return nums[0];

  if(len === 2)
  return Math.max(nums[0], nums[1]);

  // temp records the result of each call to I
  let temp;
  Prev2 records the maximum value of i-2, prev1 records the maximum value of i-1.
  let prev2 = nums[0];
  let prev1 = Math.max(nums[0], nums[1])
  for(let i = 3; i <= len; i++) {
    temp = Math.max(prev1, prev2 + nums[i-1]);
    prev2 = prev1;
    prev1 = temp;
  }

  return temp;
}
Copy the code