Climbing Stairs

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

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

Note: Given n will be a positive integer.

Example 1: Input: 2 Output: 2

Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2: Input: 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

Dynamic Programming:

As we can see this problem can be broken into subproblems, and it contains the optimal substructure property i.e. its optimal solution can be constructed efficiently from optimal solutions of its subproblems, we can use dynamic programming to solve this problem.

One can reach ith step in one of the two ways:

• Taking a single step from (i-1)th step.
• Taking a step of 2 from (i-2)th step.

So, the total number of ways to reach i​th is equal to sum of ways of reaching (i-1)th step and ways of reaching (i-2)th step.

Let dp[i] denotes the number of ways to reach on ith step.

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

int climbStairs(int n) {
    if (n == 1) return 1;

    vector<int> arr = {1, 1};
    for (int i=2; i<=n; i++) {
        arr.push_back(arr[i-1] + arr[i-2]);
    }

    return arr[n];
}

Fibonacci Number

In the above approach we have used dp array where dp[i]=dp[i-1]+dp[i-2]. It can be easily analysed that dp[i] is nothing but ith​ fibonacci number.

Fib(n) = Fib(n-1) + Fib(n-2)

Now we just have to find n​th number of the fibonacci series having 1 and 2 their first and second term respectively i.e. Fib(1)=1 and Fib(2)=2

int climbStairs(int n) {
    if (n == 1) return 1;

    int first = 1, second = 2;
    for (int i=3; i<=n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }

    return second;
}