Easy to understand Java solution with full explanation


  • 1
    T

    This is a fibonacci sequence starting with 1,2 instead of 1,1. See Pattern below:

    n_Value Solution

    <=0 0

    1 -> 1

    2 -> 2

    3 -> 3

    4 -> 5

    5 -> 8

    6 -> 13

    We see above that the number of steps at any ith step is basically the sum of the solution for the previous two steps. This is the main part of the solution. I have maintained an int array to store solutions at every step, so that it doesn't have to be calculated time and again.

    Main observation: steps[i] = steps[i-1] + steps[i-2]

    public static int climbStairs(int n) {
    
            
            // Base cases
            if(n <= 0) { return 0;}
            if(n == 1) { return 1;}
            if(n == 2) { return 2;}
            
            int[] steps = new int[n+1];
            steps[0] = 0;
            steps[1] = 1;
            steps[2] = 2;
            
            for(int i=3; i<= n; i++) {
                steps[i] = steps[i-1] + steps[i-2];
            }
            
            return steps[n];
    }

  • 3
    C

    you dont need the array to save the values. this is enough:

    // Base cases
        if(n <= 0) { return 0;}
        if(n == 1) { return 1;}
        if(n == 2) { return 2;}
    
        int a = 1;
        int b = 2;
        int c = 0;
        
        for(int i=3; i<= n; i++) {
            c = a + b;
            
            a = b;
            b = c;
        }
        
        return c;
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.