To the point

Algorithm questions are a way to test candidates’ logical thinking ability and handwritten code ability during the interview process, because there is an old saying that “it is better to write a piece of code than to talk a thousand words”.

Today we’re going to cut to the chase and talk about dynamic programming in algorithms from a real interview question about how to climb the stairs.

The interview questions,

Xiaoming has a staircase with 10 steps, each time you can climb 1 or 2 steps, ask Xiaoming how many ways to climb to the 10th step?

Why xiao Ming? That’s a strange question

Bo analysis

Many students may be confused when they encounter this problem for the first time and do not know how to solve it. The first thing we need to do is look for the key to this problem: climb one or two levels at a time.

Recursive thought

Ming can only climb one or two steps at a time, so for climbing to the 10th step, the last operation is to walk one step (at this time on the 9th step) or two steps (at this time on the 8th step). Suppose we have an expression f to calculate the way to get to a certain step, then for the tenth step the expression should be: f(10) = f(9) + f(8).

For this expression, there is a kind of instant back to the middle and high school years ~

According to the above rules, consider again, when climbing to the ninth step, the last operation is to go 1 step (at this time on the eighth step) or 2 steps (at this time on the seventh step), where the expression is: F (9) = F (8) + f(7).

.

By the time you get to the third step, the formula is f(3) = f(2) + f(1).

How many ways can you get to the second step: take one step at a time or take two steps at a time, so there are 2 ways f(2) = 2.

There must be only one way to climb to the first step: take one step and f(1) = 1.

According to our thinking logic, the relevant code is as follows:

/ * * *@method climbStairs
 * @description Climb the stairs *@param {number} N Number of stairs x@return {number} How many ways are there in total
function climbStairs (n) {
  if (n === 1) { return 1 };
  if (n === 2) { return 2 };

  let num = 0;
  num = climbStairs(n - 1) + climbStairs(n - 2);
  return num;
}

// Call the function and print the result
let num = climbStairs(10);
console.log(num); / / 89
Copy the code

Congratulations~ We have finished and got the correct result.

While you’re smiling and smirking at the interviewer, chances are the interviewer is going to get away with it and ask you how climbStairs is performing at climbStairs if n is a lot higher, say, 40.

Let’s take a look at execution performance:

The test code is as follows:

console.time();
let num = climbStairs(40);
console.log(num);
console.timeEnd()
Copy the code

My MAC configuration is as follows:

MacBook Pro Processor: 2.5ghz Quad-core Intel Core I7 RAM: 16GBCopy the code

The data is as follows:

The serial number The results of The execution time
1 165580141 811.077 ms
2 165580141 817.025 ms
3 165580141 814.803 ms

Note: There is a lag during the execution, not an instantaneous output ~ if you were doing climbStairs(100), you should hear the fan booing in an instant ~

Recursive optimization

Let’s optimize this based on the code at climbStairs above. If we carefully analyze the code execution process, we will find that there are a lot of repeated calculations. For example, f(5) will be repeated in f(6-1) and F (7-2), which wastes time and performance.

So we choose to use the space for time strategy, set the object “numbers”, and save the result of climbing a step to avoid double counting.

let numbers = {
  1: 1,
  2: 2
}
Copy the code

The optimized code is as follows:

/ * * *@method climbStairs
 * @description Climb the stairs *@param {number} N Number of stairs x@return {number} How many ways are there in total
function climbStairs (n) {
  // Store the result of the calculation, key(step) : num(way)
  let numbers = {
    1: 1.2: 2
  };

  let tmpClimbStairs = function (n) {
    // The existing data is returned directly without recalculation
    if (numbers[n]) {
      return numbers[n];
    }

    // The data does not exist
    let num = tmpClimbStairs(n - 1) + tmpClimbStairs(n - 2);
    // After the calculation, store it in numbers. You can use it next time
    numbers[n] = num;

    // Return the result
    return num;
  }

  // Calculate the result
  let num = tmpClimbStairs(n);
  // Return the result
  return num;
}
Copy the code

Under the same environment, we will perform the test again, and execute the data for three consecutive times as follows:

The serial number The results of The execution time
1 165580141 7.100 ms
2 165580141 7.478 ms
3 165580141 6.260 ms

It’s amazing! It shows that our strategy of using space for time is correct.

The results are almost instantaneous, execution is as smooth as silk stockings milk tea — at this point you can run climbStairs(100) again to experience an absolute performance spike!

This is all very well, but if you’re already feeling completely satisfied and proud of your intelligence, you’ll hear the adorable (hated) voice of your interviewer saying, “What other way or better way to do this? “

Is there a blood spout in my chest or is the interviewer doing this on purpose or is it aimed at me

Ha ha, not panic not panic, small scene ~

Recursion and recursion

Recursion and recursion are two different ways of looking at and analyzing problems.

Recursion: top-down processing logic with corresponding critical points (the point at which recursion ends);

Recursion: Bottom-up processing logic that ends at a target point.

Recursive thinking

Let’s go back to recursion.

  1. There is one way to climb to the first step. F (1) = 1;

  2. There are two ways to climb the second step: one step at a time or two steps at a time. F (2) = 2;

  3. What about climbing to the third step?

    Don’t forget the key point of our previous analysis: one or two steps at a time. For the third step, it could be from the first step or from the second step, so f(3) = f(2) + f(1).

  4. Similarly, f(4) = f(3) + f(2)

We draw a conclusion: for the NTH (N > 2) step, its expression is F (N) = F (n-1) + F (n-2). So in the process of settlement, we record the value of f(n-1) and f(n-2) each time, and migrate this value step by step to get F (N).

Now the code for climbStairs is as follows:

/** * @method climbStairs * @description climbStairs * @param {number} n number of steps * @return {number} number of ways */ function ClimbStair (n) {// If (n <= 2) {return n; } else {// for n > 2 let I = 1; F (n-2) let j = 2; f(n-2) let j = 2; // F (n-1) = f(n-1); // define the path num let num; // From level 3, execute loop for (let k = 3; k <= n; k++) { // f(N) = f(N-1) + f(N-2) num = i + j; // Change the value of f(n-1) to f(n-2) I = j; // set the current value to f(n-1) j = num; } return num; }}Copy the code

This time we directly reduced the time complexity, to O(N), the implementation is more like that, smooth, smooth ~

Let’s take a look at the results of three consecutive tests:

The serial number The results of The execution time
1 165580141 6.570 ms
2 165580141 6.647 ms
3 165580141 6.658 ms

Compared with the recursive implementation, the recursive implementation is lower in time complexity and more efficient

This is the moment when the stair climbing question is finally answered and the interviewer will look at you the way a mother-in-law looks at her son-in-law.

The algorithmic problem of dynamic programming takes many different forms, and stair climbing is one of them. Here Brother Hu will leave you an interview question, to see if you have a deep understanding of dynamic programming.

The real interview questions are as follows:

You are a bandit of faith, there is a row of houses waiting for you to rob, you can not rob adjacent houses, only one or more houses apart to rob, the money in the houses are non-negative integers, the data format is as follows: [3, 4, 5, 2, 1, 1], please calculate the maximum amount of money you can rob.

The robber had a lot of faith and didn’t take them all

Welcome to leave a comment, talk about your understanding of dynamic programming, leave the answer to this interview question, discuss and exchange ~

Afterword.

The above is brother Hu to share the content today, like partners remember to like, collect ah, pay attention to Brother Hu has words, learning front end don’t get lost, welcome a lot of messages exchange…

Hu Ge has words, focus on the field of front-end technology, share front-end system architecture, framework implementation principle, the latest and most efficient technology practice!