Brush questions, climb stairs, recursion, backtracking, dynamic programming_My blog is gone

class=”markdown_views prism-atom-one-dark”>

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge

Click the blue word above to follow me, let’s learn programming together
Welcome friends to share, repost, private message, appreciate.

Today, I will share a ByteDance interview question: Stair Climbing Ⅱ.

Description of topic:

A step has a total of n levels. If you can skip 1 level at a time, you can also skip 2 levels, but cannot be continuous Skip 2 levels twice. Find how many total jumps there are in total.

Analysis:

If there is no constraint of “cannot jump 2 levels twice in a row”, then we can easily write the following recursive function:

int climb(int n)
 {
     
     if (n == 1 || n == 2) {
     
         return n;
     }

     return climb(n - 1) + climb(n - 2);
 }
 

In the above code, it is bound to include the method of jumping 2 levels twice in a row. So, we try to remove these redundant jumps.

To get rid of these jumps, we need to get rid of twice, three, four times… jump 2 level jumping method, in this way, the problem is bound to become extremely complicated.

Let’s change the way of thinking: You can’t skip 2 level twice in a row, in other words, jump 2 You can only skip 1 level after level. Then, we will encapsulate “jump 1 level after skipping 2 level” into a whole – 3 level.

In this way, the title is equivalent to: A step has a total of n levels. If you can skip 1 level at a time, you can also skip Level 3, . Find how many total jumps there are in total.

We can easily write the following code:

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge

int climb(int n)
 {
     
     if (n == 1 || n == 2 || n == 3) {
     
         return n;
     }

     return climb(n - 1) + climb(n - 3);
 }
 

At this point in the analysis, the problem has been solved. In order to avoid some friends’ doubts about the correctness of this solution, we use the most stupid backtracking to verify it.

#include 
 using namespace std;

 int climb(int n)
 {
     
     if (n == 1 || n == 2 || n == 3) {
     
         return n;
     }

     return climb(n - 1) + climb(n - 3);
 }

 // backtracking method
 int climb_test(int now, int all,  bool jmp2)
 {
     
     int cnt = 0;

     if (now == all) {
      // reach the end point, add one to the number
         ++cnt;
         return cnt;
     }

     if (now  all) {
      // Jump too much, return directly
         return cnt;
     }

     // not reached the end

     cnt += climb_test(now + 1,  all, false); // Skip 1 level and reset the "jump 2 level" flag
    
     if (!jmp2) {
     
         cnt += climb_test(now + 2,  all, true); // Jump 2 levels, and set the "jump 2 levels" flag
     }

     return cnt;
 }

 int main()
 {
     
     string info = "correct";
    
     for (int i = 1; i   50; ++i) {
     
         int num1 = climb(i);
         int num2 = climb_test(0, i,  false);

         if (num1 != num2) {
     
             info = "error";
             break;
         }
     }

     cout << info << endl;

     return 0;
 }
 

Compile and run:

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge

jincheng@#:$ g++ test.cpp -o test
 jincheng@#:$ ./test
 correct
 

It can be seen that the code we wrote is correct.

In fact, the recursive method is an algorithm that consumes a lot of resources, mainly for the dynamic generation and switching of function stacks. Below we use the dynamic programming method to rewrite the code of the recursive method.

Dynamic programming is actually a method of exchanging space for time. We save the solutions of subproblems, so that repeated subproblems only need to be calculated once , thus optimizing the time complexity of the algorithm.

int climb_dp(int n)
 {
     
     vectorint dp(n+1  ); // Save the solution of the sub-problem, dp[i] means  The total jumping method of the i-level stairs
     dp[1] = 1; // initialization
     dp[2true); // Jump 2 levels, and  Set the "Skip 2 levels" flag
     }

     return cnt;
 }

 int main()
 {
     
     string info = "correct";
    
     for (int i = 1; i   50; ++i) {
     
         int num1 = climb(i);
         int num2 = climb_test(0, i,  false);

         if (num1 != num2) {
     
             info = "error";
             break;
         }
     }

     cout << info << endl;

     return 0;
 }
 

Compile and run:

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge

jincheng@#:$ g++ test.cpp -o test
 jincheng@#:$ ./test
 correct
 

It can be seen that the code we wrote is correct.

In fact, the recursive method is an algorithm that consumes a lot of resources, mainly for the dynamic generation and switching of function stacks. Below we use the dynamic programming method to rewrite the code of the recursive method.

Dynamic programming is actually a method of exchanging space for time. We save the solutions of subproblems, so that repeated subproblems only need to be calculated once , thus optimizing the time complexity of the algorithm.

int climb_dp(int n)
 {
     
     vectorint dp(n+1  ); // Save the solution of the sub-problem, dp[i] means  The total jumping method of the i-level stairs
     dp[1] = 1; // initialization
     dp[2] = 2;
     dp[3] = 3;

     for (int i = 4; i <= n; ++i) {
     
         dp[i] = dp[i - 1]  span> + dp[i - 3];
     }

     return dp[n];
 }
 

Okay, today’s content is here! If you don’t understand, please feel free to send me a private message for consultation, I will know everything!

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge

an>] = 2;
dp[3] = 3;

for (int i = 4; i <= n; ++i) {

dp[i] = dp[i – 1] span> + dp[i – 3];
}

return dp[n];
}

Okay, today’s content is here! If you don’t understand, please feel free to send me a private message for consultation, I will know everything!

WeChat search: programming notebook, get more dry goods knowledge
WeChat search: programming notebook, get more dry goods knowledge
WeChat search : Programming notebook, get more dry goods knowledge