Both bottom-up and top-down dynamic programming style Java code. Good for learners.


  • 6
    Y

    The bottom-up approach is provided as following.
    The idea is that we consider from stair level 0 and stair level 1, which are the base cases. And we use an array N to record the number of distinct ways for each level.
    Obviously, for level 0 and level 1, the number of distinct ways are 1. After that, for each level i where i is greater than 0 and 1, we have 2 possible way to step on it: The first one is to go from level i - 1 (i.e. climb 1 steps); the second one is to go from level i - 2 (i.e. climb 2 steps). Thus for each level i where i is greater than 1, N[i] = N[i - 1] + N[i - 2].
    And hence, N[n] stores the total number of distinct ways to climb n stairs after the for loop.

    /*
    bottom-up approach
    */
    
    public int climbStairs(int n){
        if (n == 0){
            return 1;
        }
        else{
            int[] N = new int[n + 1];
            N[0] = 1;
            N[1] = 1;
            for (int i = 2; i <= n; i ++){
                N[i] = N [ i - 1] + N[i - 2];
            }
            return N[n];
        }
    }
    

    The top down approach is showed as following.
    In the top down approach, we actually consider from the top, which is stair level n. And the recursive equation is still N[i] = N[i - 1] + N[i - 2]. Hence we get the so-called optimal substructures in Dynamic programming. Thus, by recursively calculate each level from n to base case, which is 0 and 1 and memorize the intermediate, we can still get the total number of distinct ways to go to stair n.

    /*
    top-down approach
    */
    
    
    public int climbStairs(int n) {
        int[] N = new int[n];
        for (int i = 0; i < n; i++){
            N[i] = -1;
        }
        
        return topdownclimbStairs(n, N);
    }
    
    private int topdownclimbStairs(int n, int[] N){
        if (n == 0 || n == 1){
            return 1;
        }
        
        if (N[n - 1] >= 0){
            return N[n - 1];
        }
    
        else {
            N[n - 1] = topdownclimbStairs(n-1, N) + topdownclimbStairs(n - 2, N);
            return N[n - 1];
        }
    }
    

  • 0
    M

    Thanks for your share!It is what i need


  • 0
    G

    This should return 0 if n is == 0. There are 0 ways to climb a set of stairs 0 steps high.


  • 0
    Y

    Yes, that's reasonable. However, I return 1 because that is what returned by latched system. You can test this by using 0 as the test case.


  • 0
    A

    An explanation would be nice


  • 1
    Y

    @algogator Thanks for your suggestion. Already added it to the solution. See the modified version.


Log in to reply
 

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