Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continues to punch card 22 days 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

The sample1Input:2Output:2Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2 阶
Copy the code
The sample2Output:3Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3.  2Order +1 阶
Copy the code

🌻C# method: dynamic programming

Thinking analytical

The ultimate goal is to find all the ways to climb up the stairs

Obviously, this problem can be solved by dynamic programming, so if you want to find order N, you need to find order N-1

So using dynamic programming makes it easy to find a solution. Let’s take a look at the code

Code:

public class Solution {
public int ClimbStairs(int n)
{
    if (n < 3) return n;
    int f1 = 1, f2 = 2, f3 = f1 + f2;
    for (int i=3; i <= n; i++) { f3 = f1 + f2; f1 = f2; f2 = f3; }returnf3; }}Copy the code

The execution result

By execution time:32Ms, in all C# beat 95.36% of users in submissionMemory consumption:15.1MB, in all C# beat 5.84% of users in submission
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java Method 1: Dynamic planning

Thinking analytical

Code:

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        returnr; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:35.1MB, beat out all Java commits69.63% of the userCopy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java method two: Matrix fast powers

Thinking analytical

This method is to buckle the official answer, put in this for your reference. 

public class Solution {
    public int climbStairs(int n) {
        int[][] q = {{1.1}, {1.0}};
        int[][] res = pow(q, n);
        return res[0] [0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1.0}, {0.1}};
        while (n > 0) {
            if ((n & 1) = =1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2] [2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]; }}returnc; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:35.2MB, beat out all Java commits50.69% of the userCopy the code

Complexity analysis

Time complexity: O(longN) Space complexity: O(1)
Copy the code

💬 summary

  • Today is the twenty-second day of buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!