Recursive Staircase | Climbing Stairs Problem

Problem Statement :

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?

Solution :

Approach 1: Brute Force
Algorithm

In this brute force approach we take all possible step combinations i.e. 1 and 2, at every step. At every step we are calling the function climbStairsclimbStairs for step 11 and 22, and return the sum of returned values of both functions.

climbStairs(i,n)=(i + 1, n) + climbStairs(i + 2, n)climbStairs(i,n)=(i+1,n)+climbStairs(i+2,n)

where i defines the current step and nn defines the destination step.


class Solution {
   
    public int climbStairs(int n) {
       
        if(n<=1)
            return 1;
        else{
            int fib[]=new int[3];
            fib[0]=1;
            fib[1]=1;
            for(int i=2;i<=n;i++){
                fib[2]=fib[0]+fib[1];
                fib[0]=fib[1];
                fib[1]=fib[2];
            }
            return fib[2];
        }
    }
}

Note: Here the problem resembles to Fibonacci Series, where the current solution can be derived from the earlier solutions.
Just to optimise it further i am just maintaining the previous two solutions, otherwise we could have maintained all the prior solutions as well.