70. Climbing Stairs

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?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

• 1 <= n <= 45

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        vector<int> t(n+1);
        if(n<=1){
            return n;
        }
        t[1] = 1;
        t[2] = 2;
        for(int i=3; i<=n; i++ ){
            t[i] = t[i-1] + t[i-2];
        }
        return t[n];
    }
};

from typing import *
import collections

class Solution:
    def climbStairs(self, n: int) -> int:
        t = [0]*46
        t[1] = 1
        t[2] = 2

        if(n==1 or n==2):
            return n

        for i in range(3,n+1):
            t[i] = t[i-1] + t[i-2]

        return t[n]

Time Complexity:

• The time complexity of the climbStairs function is \( O(n) \), where \( n \) is the input integer representing the number of stairs.
• The for loop runs from 3 to \( n \), performing constant time operations in each iteration, leading to a linear time complexity.

Space Complexity:

• The space complexity of the climbStairs function is \( O(1) \).
• The array t has a fixed size of 46 elements, and thus the space used does not depend on the input size \( n \).
• Other than the array t, the function uses a constant amount of space for variables and operations, contributing to an overall space complexity of \( O(1) \).

Approach 02:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int t[46];

    int solve(int n){

        if(n<1) return 0;
        if(n==2 or n==1) return n;

        if(t[n] != -1){
            return t[n];
        }
        
        return t[n] = solve(n-1) + solve(n-2);
    }

    int climbStairs(int n) {
        memset(t, -1, sizeof(t));
        return solve(n);
    }
};

from typing import *

class Solution:
    t = [-1]*46
    def solve(self, n):
        if(n<1):
            return 0
        if n==1 or n==2:
            return n

        if(self.t[n]!= -1):
            return self.t[n]
        self.t[n] = self.solve(n-1) + self.solve(n-2)
        return self.t[n]

    def climbStairs(self, n: int) -> int:
        return self.solve(n)

Time Complexity:

• The time complexity of the climbStairs function is \( O(n) \), where \( n \) is the input integer representing the number of stairs.
• Each distinct value of \( n \) is computed only once due to memoization, ensuring that the total number of recursive calls is linear with respect to \( n \).

Space Complexity:

• The space complexity of the climbStairs function is \( O(n) \).
• While the memoization array t has a fixed size, the recursion call stack depth can reach up to \( n \), contributing to the space complexity.

Approach 03:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        int n1 = 1;
        int n2 = 2;
        if(n==1 or n==2){return n;}
        for(int i=3; i<=n; i++){
            n2 = n1+n2;
            n1 = n2 - n1;
        }
        return n2;
    }
};

from typing import *

class Solution:
    def climbStairs(self, n: int) -> int:
        n1, n2 = 1, 2

        if(n==1 or n==2):
            return n
        
        for i in range(3,n+1):
            n2 = n1 + n2
            n1 = n2 - n1

        return n2

Time Complexity:

• The time complexity of the climbStairs function is \( O(n) \), where \( n \) is the input integer representing the number of stairs.
• The for loop executes \( n-2 \) times, leading to a linear time complexity.

Space Complexity:

• The space complexity of the climbStairs function is \( O(1) \).
• The function uses a constant amount of space, maintaining only two variables, regardless of the input size.