1. The subject

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.

Example 1:

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

  1. 1 order plus 1 order
  2. 2 order

Example 2:

Input: 3

Output: 3

Explanation: There are three ways to climb to the top.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

2. The answer

2.1 Idea 1 (Recursion)

It’s pretty obvious that you can do it recursively, by breaking the problem down into smaller sub-problems

  • Recursive formula: F (n) = F (n-1) + f(n-2)
  • Termination conditions: When n==1, there is only one way, when n==2, there can be (1, 1) and (2) two ways

The code is as follows:

class Solution {
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        return climbStairs(n - 1) + climbStairs(n - 2); }}Copy the code

The submission fails, and the time limit is exceeded when n==45, which is just a warning of possible problems with recursion:

Beware of stack overflow

Function calls use stacks to calculate and hold temporary variables. Each recursive call creates temporary variables that are pushed into memory in the form of stack frames, which can cause stack overflows when the recursion level is too deep.

Beware of double counting

In this case, f(5) = f(4) + f(3), f(6) = f(5) + f(4), both processes calculate f(5) and f(4), respectively. Other layers also use repeated calculations, resulting in wasteful situations. Therefore, caching can be used to avoid double calculations.

The code after transformation:

class Solution {
    Map<Integer, Integer> mCache = new HashMap<>();
    public int climbStairs(int n) {
        if(n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }

        if (mCache.containsKey(n)) {
            return mCache.get(n);
        }

        int cache = climbStairs(n - 1) + climbStairs(n - 2);
        mCache.put(n, cache);
        returncache; }}Copy the code

Time complexity

So if you use a recursive tree, every node is divided into two values f(n-1) and F (n-2), each time minus 1 or minus 2. The data size of the leaf node is 1 or 2. So the longest path is about n, and the shortest path is about n over 2

If both path lengths are N, then the total number of calculations n is:

If both path lengths are N, then the total number of computations n/2 is:

The average time complexity should be somewhere in between.

The optimized code avoids a lot of repeated calculation, and the time complexity is proportional to N, that is, O(n).

Spatial complexity

The space complexity is the height of the tree: O(n)

Submit the results