Climbing Stairs

My approach:

We can observe a recurrence relation that exists and we can easily solve it by using recursion. On observation, we can see there are overlapping subproblems. To solve that we will use memoization.

Instead of using the top-down approach, we can also solve it using the bottom-up approach by simply using one loop.

My solution:

• Recursive

• Iterative

Code:

• Recursion with Memoization

class Solution {
public:
    int helper(int n, int* arr){
        if( n==0){
            return 1;
        }
        if(n<=2){
            return n;
        }

        if(arr[n]!=-1){
            return arr[n];
        }

        int a = helper(n-1,arr);
        int b = helper(n-2,arr);
        arr[n] = a+b;
        return arr[n];
    }

    int climbStairs(int n) {
        int arr[n+1];

        for(int i=0;i<=n;i++){
            arr[i] = -1;
        }

        int output = helper(n,arr);
        return output;
    }
};

• Dynamic Programming

class Solution {
public:
    int helper(int n, int* arr){
        if( n==0){
            return 1;
        }
        if(n<=2){
            return n;
        }

        if(arr[n]!=-1){
            return arr[n];
        }

        int a = helper(n-1,arr);
        int b = helper(n-2,arr);
        arr[n] = a+b;
        return arr[n];
    }

    int climbStairs(int n) {

        if(n==0){
            return 1;
        }
        if(n<=2){
            return n;
        }

        int arr[n+1];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;

        for(int i=3;i<=n;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }

        return arr[n];
    }
};