Java 0ms, O(n) time and O(1) space solution


  • 0
    W

    The bottom-up DP solution is not as easy as the top-down DP solution, but it is not too hard to come up with:
    ...

    public int climbStairs(int n) {
        
        int[] map = new int[n+1];
        map[0] = 1;
        if(map.length > 1){map[1] = 1;}
        for(int i=2; i<=n; i++){
            map[i] = map[i-1] + map[i-2];
        }
        
        return map[n];
    }
    

    ....

    But observe that we don't need to maintain all n+1 int since at each iteration, we only need two int, namely map[i-2] and map[i-1] to determine map[i].

    Instead, we only need to maintain 3 int.
    ...

    public int climbStairs(int n) {
        
        int[] map = new int[3];
        map[0] = 1;
        map[1] = 1;
        map[2] = 1;
        for(int i=2; i<=n; i++){
            map[2] = map[1] + map[0];
            map[0] = map[1];
            map[1] = map[2];
        }
        
        return map[2];
    }
    

    ...


Log in to reply
 

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