Accepted Java climbing stairs solution


  • 2
    V

    public class Solution {

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

    }


  • 1

    Actually, your algorithm don't need O(n) space, just keep result and two steps before value is enough.

    public class Solution {
        public int climbStairs(int n) {
            if(n < 3){
                return n;
            }
            int twoStepBefore = 1;
            int oneStepBefore = 2;
            int result = 3;
            for(int i = 3; i <= n; i++){
                result = twoStepBefore + oneStepBefore;
                twoStepBefore = oneStepBefore;
                oneStepBefore = result;
            }
            return result;
        }
    }

Log in to reply
 

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