[C++] Leetcode 70. Climbing Stairs (Hint, Solution)

Problem

https://leetcode.com/problems/climbing-stairs/ 

Climbing Stairs - LeetCode

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

 

 

 

Hint

Use Dynamic Programming.

 

 

 

Solution

1. Recursive + Memorization
2. Tabulation

 

 

 

Code

Simple

1. Recursive + Memorization

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(50,-1);
        dp[0] = 1;
        dp[1] = 1;
        return recursive(n, dp);
    }
    int recursive(int n, vector<int> &dp) {
        if (dp[n] != -1)
            return dp[n];

        dp[n] = recursive(n-1, dp) + recursive(n-2, dp);
        return dp[n];
    }
};

2. Tabulation

class Solution {
public:
    int climbStairs(int n) {
        int a = 0;
        int b = 1;
        int answer;
        for (int i=1; i<n+1; i++) {
            answer = a+b;
            a = b;
            b = answer;
        }

        return answer;
    }
};

 

Whole Code with Test Case

// https://leetcode.com/problems/climbing-stairs
#include <iostream>

using namespace std;

class Solution {
public:
    int climbStairs(int n) {
        int a = 0;
        int b = 1;
        int answer;
        for (int i=1; i<n+1; i++) {
            answer = a+b;
            a = b;
            b = answer;
        }

        return answer;
    }
};


int main() {
    Solution s = Solution();
    cout << endl << s.climbStairs(45) << endl;

    return 0;
}

 

 

 

Complexity

Time

1. Recursive + Memorization: O(n)
2. Tabulation: 2 * O(n)

 

Space

1. Recursive + Memorization: O(n)
2. Tabulation: O(n)

 

 

 

Best Solution (Pinned)

 

 

 

Overall