0ms simple Java solutions


  • 0
    L
    public class Solution {
    public int climbStairs(int n) {
        /**
         * ways[i] denotes # of ways to get to ith step
         * corner case: ways[0]=1, ways[1] = 2(one 2 steps or two 1 step)
         * general case: ways[i] = ways[i-2]+ways[i-1]
         * */
         if(n == 0) return 0;
         if(n == 1) return 1;
         if(n == 2) return 2;
         int[] ways = new int[n];
         ways[0] = 1; ways[1] = 2;
         for(int i = 2;i<n;i++) ways[i] = ways[i-2]+ways[i-1];
         return ways[n-1];
    }
    

    }

    improvement: use two variables to store ways[i-1] and ways[i-2] instead of maintaining the whole array, space O(1), time O(n)

        public int climbStairs(int n) {
         if(n == 0) return 0;
         if(n == 1) return 1;
         if(n == 2) return 2;
         int minusTwo = 1, minusOne = 2, current = minusOne;
         for(int i = 2;i<n;i++) {
             current = minusTwo+minusOne;
             minusTwo = minusOne;
             minusOne = current;
         }
         return current;
    }

Log in to reply
 

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