LeetCode #70 Climbing Stairs Solution & Explanation

LeetCode Problem

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Fibonacci

This question is a classic Fibonacci example.

However, you may have seen this picture.

If you scrutinize this picture carefully, you can find out some logic.

The two smaller numbers add up to the next number.

2 = 1+1

3 = 2+1

5 = 3+2

8 = 5+3

Isn’t that similar to the problem above?

Want to know more about Fibonacci Number definition ,here it is (wiki).

Solution

Let’s presume the solution function as Fn(n).

And let’s list out what we know.

• n = 1，just have one way ➔ 1
• n = 2，just two ways ➔ 1+1 or 2

Think about what will happen when n = 3

First, we only have two choices (one step or two steps). Is that right?

If we choose

• one step ➔ two steps left
• two steps ➔ one step left

When we know either one or two steps left, we know how many ways to go to the top.

So, we can write as

• one step ➔ two steps left Fn(2)= 2
• two steps ➔ one step left Fn(1)= 1

The answer of Fn(3) = Fn(2)+Fn(1) = 2+1 = 3

Next, let’s try n = 4

Same as above, we only have two choices (one step or two steps) at first

• one step ➔ three steps left Fn(3) = 3 (the answer we have just gotten above)
• two steps ➔ two steps left Fn(2) = 2

So, we can get the answer of Fn(4) = Fn(3)+Fn(2) = 3+2 = 5

Now, we can find out the rule of this problem.

Let’s try n as n for the last time

• one step ➔ n-1 steps left Fn(n-1)
• two steps ➔ n-2 steps left Fn(n-2)

⭐We can get the conclusion ➔ Fn(n) = Fn(n-1) + Fn(n-2)

Now, let’s turn the conclusion to simple programming language.

C# Solution

Solution1 (use the temporary interger)

public class Solution {
    public int ClimbStairs(int n) {

        //the first example has tell us how many distinct way for 1 or 2 steps stairs
        int first  = 1;     
        int second = 2;     
        int tmp = 0;        
        
        if(n<=2)    //if n not more than 2 than just return the stpes it take
        {
            return n;
        }
        else
        {
            for(int i =3; i<=n;i++) //every iteration,will add the last two steps together and save as 'second'
            {
                tmp = second;       
                second+=first;      //set second as now iteration needed steps
                first = tmp;        //set first as the last time needed steps
            }
        }
        return second;
    }
}

Solution2 (use the array to store)

public class Solution {
    public int ClimbStairs(int n) {

        if(n<2){
            return n;
        }
        
        int[] ans = new int[n];
        ans[0] = 1;
        ans[1] = 2;
        
        for(int i=2;i<n;i++) {
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[n-1];
    }
}

Java Solution

Solution1 (use the temporary interger)

class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return n;
        }
        
        int first  = 1;  
        int second = 2;   
        int tmp = 0;   
        
        for(int i =3; i<=n;i++) {
            tmp = second;       
            second+=first;    
            first = tmp;       
         }
        return second;
        
    }
}

Solution2 (use the array to store)

class Solution {
    public int climbStairs(int n) {
        if(n<2){
            return n;
        }
        
        int[] ans = new int[n];
        ans[0] = 1;
        ans[1] = 2;
        
        for(int i=2;i<n;i++) {
            ans[i]=ans[i-1]+ans[i-2];
        }
        return ans[n-1];
    }
}

Python3 Solution

use list to store

class Solution:
    def climbStairs(self, n: int) -> int:
        
        if(n<2):
            return n;
        
        ans = [1,2];
        
        for i in range(2, n):
            ans.append(ans[i-1]+ans[i-2]);
            
        return ans[n-1];

JavaScript Solution

use array to store

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let arr = [1,2];
    for (var i = 2; i<n; i++) {
        arr[i]=arr[i-1]+arr[i-2];
    }
    return arr[n-1];
};

Conclusion

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad, Thanks a lot !

"You don't have to see the whole staircase, just take the first step."
                                                                                    Martin Luther King, Jr.

Cover Photo – Photo by Ludde Lorentz on Unsplash

Technology Article

• Understanding Hive ransomware – Preventing becoming the next victim2023-07-24
• How to Effectively Manage Personnel Permissions using Binary-Base Logic Control2023-04-04
• Zambian Central Bank refused to pay ransom to hackers but sent pornographic picture !2022-06-06

Latest Post

• LeetCode #2073 Time Needed to Buy Tickets Solution & Explanation
• LeetCode #1700 Number of Students Unable to Eat Lunch Solution & Explanation
• LeetCode #1544 Make The String Great Solution & Explanation
• LeetCode #977 Squares of a Sorted Array Solution & Explanation
• LeetCode #283 Move Zeroes Solution & Explanation