Number of unique ways to climb the staircase

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

• 1, 1, 1, 1
• 2, 1, 1
• 1, 2, 1
• 1, 1, 2
• 2, 2

Example:

Input:  n = 4
Output: 5

Approach 1: Using Recursion

C++

#include <bits/stdc++.h>
using namespace std;

int countWays(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    return countWays(n - 1) + countWays(n - 2);
}
int main()
{
    int n = 4;
    cout << countWays(n);

    return 0;
}

Approach 2: Using Dynamic Programming (Memoization)

C++

#include <bits/stdc++.h>
using namespace std;

int dp[1000];

int countWays(int n)
{
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    if (dp[n] != -1)
        return dp[n];
    dp[n] = countWays(n - 1) + countWays(n - 2);
    return dp[n];
}
int main()
{
    int n = 4;

    memset(dp, -1, sizeof(dp));
    cout << countWays(n);

    return 0;
}

Approach 3: Using Dynamic Programming (Tabular)

C++

#include <bits/stdc++.h>
using namespace std;

int countWays(int n)
{
    int dp[n + 1];
    if (n == 1)
        return 1;
    if (n == 2)
        return 2;
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}
int main()
{
    int n = 4;

    cout << countWays(n);

    return 0;
}