C++ - Ways to Reach the n’th Stair

Problem Statement

Given the n stairs, you can climb either 1 or 2 steps at a time.

Find the total number of ways to reach the nth stair.

Example 1:

Input: n = 3

Output: 3

Explanation:

1. (1,1,1)

2. (1,2)

3. (2,1)

Example 2:

Input: n = 4

Output: 5

Explanation:

1. (1,1,1,1)

2. (1,1,2)

3. (1,2,1)

4. (2,1,1)

5. (2,2)

Approach 1: Recursion (Exponential Time Complexity)

At each step, you can take 1 step or 2 steps.

Use recursion to explore all possible ways.

Code Implementation

#include <iostream>

using namespace std;

int countWays(int n) {

    if (n == 0) return 1;  // Reached the top

    if (n < 0) return 0;   // Invalid step

    return countWays(n - 1) + countWays(n - 2);

}

int main() {

    int n = 4;

    cout << "Ways to reach " << n << "th stair: " << countWays(n) << endl;

    return 0;

}

Time Complexity:

O(2^N) (Exponential growth, slow for large n).

Space Complexity:

O(N) (Recursive call stack).

Approach 2: Memoization (Top-Down DP, O(N) Time, O(N) Space)

Store results of subproblems in an array to avoid redundant calculations.

Code Implementation

#include <iostream>

#include <vector>

using namespace std;

int countWaysMemo(int n, vector<int>& dp) {

    if (n == 0) return 1;

    if (n < 0) return 0;

    if (dp[n] != -1) return dp[n];

    dp[n] = countWaysMemo(n - 1, dp) + countWaysMemo(n - 2, dp);

    return dp[n];

}

int countWays(int n) {

    vector<int> dp(n + 1, -1);

    return countWaysMemo(n, dp);

}

int main() {

    int n = 4;

    cout << "Ways to reach " << n << "th stair: " << countWays(n) << endl;

    return 0;

}

Time Complexity:

O(N) (Each n is calculated only once).

Space Complexity:

O(N) (For the memoization array).

Approach 3: Bottom-Up Dynamic Programming (O(N) Time, O(N) Space)

Use iteration instead of recursion.

Store results in an array.

Code Implementation

#include <iostream>

#include <vector>

using namespace std;

int countWays(int n) {

    if (n == 0) return 1;

    if (n == 1) return 1;

    vector<int> dp(n + 1, 0);

    dp[0] = 1;

    dp[1] = 1;

    for (int i = 2; i <= n; i++) {

        dp[i] = dp[i - 1] + dp[i - 2];

    }

    return dp[n];

}

int main() {

    int n = 4;

    cout << "Ways to reach " << n << "th stair: " << countWays(n) << endl;

    return 0;

}

Time Complexity:

O(N) (Iterates once).

Space Complexity:

O(N) (Stores all results in an array).

Approach 4: Space Optimized DP (O(N) Time, O(1) Space)

Since dp[i] = dp[i-1] + dp[i-2], we only need the last two values.

Use two variables instead of an array.

Code Implementation

#include <iostream>

using namespace std;

int countWays(int n) {

    if (n == 0) return 1;

    if (n == 1) return 1;

    int prev1 = 1, prev2 = 1, curr = 0;

    for (int i = 2; i <= n; i++) {

        curr = prev1 + prev2;

        prev2 = prev1;

        prev1 = curr;

    }

    return curr;

}

int main() {

    int n = 4;

    cout << "Ways to reach " << n << "th stair: " << countWays(n) << endl;

    return 0;

}