Easy solutions for suggestions.


  • 49
    T

    Hi guys, I come up with this arithmetic way. Find the inner logic relations and get the answer.

    public class Solution {
    
    public int climbStairs(int n) {
        if(n == 0 || n == 1 || n == 2){return n;}
        int[] mem = new int[n];
        mem[0] = 1;
        mem[1] = 2;
        for(int i = 2; i < n; i++){
            mem[i] = mem[i-1] + mem[i-2];
        }
        return mem[n-1];
    }
    

    }


  • 6
    M

    Nice work. About the only weakness here versus the recursive map version is that this one does not store previous results, so will always take O(n) to return an answer.

      ArrayList<Integer> map = new ArrayList<Integer>();
      public int climbStairs(int n){
        if(n == 0 || n == 1 || n == 2){return n;}
        if(map.size() >= n) return (map.get(n-1)).intValue();
        if(map.size() < 2){
          map.add(0,new Integer(1));
          map.add(1,new Integer(2));
        }
        for(int i = map.size(); i < n; i++){
          map.add(i,map.get(i-1)+map.get(i-2));  
        }
        return (map.get(n-1)).intValue();
      }
    

    EDIT: As a nod to ehab, here's the complicated math way:

    static double root5 = Math.sqrt(5);
    static double phi = (1+root5)/2;
    public int climbStairs(int n) {
        return (int)Math.floor( (Math.pow(phi,n+1)/root5) + 0.5 );
    }
    

    And yes, that's been accepted.


  • 3
    S

    Good job. I spent a while to figure out the arithmetic relations in different steps. Yet I made some effort to look into this problem in a different way, and it seems to be more reasonable logically. Please check the description in my codes.

    class Solution {
    public:
    /* let's think about the problem as a binary string
     * we start from position S[0] and end at S[n]
     * we have n+1 steps as S[0, 1, 2, ..., n] and S[0]=S[n]=1
     * then 1-step is [...1...] and 2-step is [...0, 1...];
     * in the string, each 0 must be followed by 1
     * while each 1 could be followed by either 0 or 1
     * then the answer is to find how many paths at each position
    */
    int climbStairs(int n) {
        // simple cases
        if (n <= 1)
            return n;
            
        int cur_step = 1;
        int ones = 1; // since S[0]=1 as the base case
        int zeros = 0;
        int ways = 0; 
        
        // we walk through S[1] to S[n-1]
        while (cur_step < n) {
            ways = 2*ones + zeros;
            zeros = ones;
            ones = ways - zeros;
            cur_step ++;
        }
        return ways;
    }
    

    };


  • 0
    E

    i don't understand at all the string zeros and ones solution, but for the recursive map solution, if u have a closer look, u will find that you are just implementing Fibonacci series, which is the easiest correct solution for this problem


  • 0
    M

    Which means there is a closed-form solution. Good observation.


  • 4
    G
    class Solution:
    # @param n, an integer
    # @return an integer
    def climbStairs(self, n):
        if n in range(3):
            return n
        fib = [1, 2]
        for i in range(2, n):
            fib.append(fib[i - 1] + fib[i - 2])
        return fib[n - 1]
    

    Python is elegant.


  • 82
    F

    No need to store every middle result.
    actually, you just need to store 2 of them.
    so we can solve this in o(n) and o(1)

    public int climbStairs(int n) {
        if(n==0||n==1) return  1;
        int stepOne=1,stepTwo=1;
        int result=0;
        for(int i=2;i<=n;i++){
            result=stepOne+stepTwo;
            stepTwo=stepOne;
            stepOne=result;
        }
        return result;
    }

  • 2
    W

    I thought it could be solved using the idea of formulating a fibnacci sequence.
    Therefore, the problem could be solved in linear complexity using extra memory O(1).


  • 0
    T

    Exactly, so far I think this is the best solution!


  • 4
    C

    A normal DP recursive way.

    static HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    public static int climbStairs(int n) {
    	if(map.containsKey(n)) return map.get(n);
    	else if(n == 1) return 1;
    	else if(n == 2) return 2;
    	else {
    		int n1 = climbStairs(n - 1);
    		int n2 = climbStairs(n - 2);
    		map.put(n - 1, n1);
    		map.put(n - 2, n2);
    		return n1 + n2;
    	}
    }	

  • 0
    Z

    look at this.

        public int climbStairs_0(int n) {
            if (n < 0)
                return 0;
            if (n == 1)
                return 1;
            if (n == 2)
                return 2;
            return climbStairs_0(n - 1) + climbStairs_0(n - 2);
        }
    

    to comput N(N>2), wo can add the result of N-1(last climb is 1 step) and the result of N-2(last climb is 2 steps).

    So , it looks like Fibonacci Sequence.

    we can use loop or math to resolve it.

    here is my solution

        public int climbStairs(int n) {
            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 = 0; i < n - 2; i++) {
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }

  • 1
    Z

    simple code.

        public int climbStairs(int n) {
            int a = 0;
            int b = 1;
            while (n-- > 0) {
                int c = a + b;
                a = b;
                b = c;
            }
            return b;
        }

  • 4
    C
    // fibnacci sequence
    int climbStairs(int n) {
        int a = 1, b = 1;
        while(--n >= 1){
            a += b;
            b = a - b;
        }
        return a;
    }
    

  • 0
    M

    Pretty nice solution.


  • 0
    V
    class Solution(object):
        def climbStairs(self, n):
            """
            :type n: int
            :rtype: int
            """
            a = 1
            b = 2
            if n <= 2: return n
            for i in range(n-2):
                a, b = b, a + b
            return b

  • 0
    C

    What are mem[0] and mem[1] represent?


  • 0
    V

    3 line O(1) memory solution

    public int climbStairs(int n) {
        int answer = 1;
        for(int i = 0, pre = 0; i < n; i++) pre = (answer += pre) - pre;
        return answer;
    }

  • 0
    D
    if(n == 0 || n == 1 || n == 2){return n;}
    int[] f = new int[n + 1]; 
     f[2] = 2; f[1] = 1; f[0] = 0;
        for(int i = 3; i <= n; i++){
            f[i] = f[i - 1] + f[i - 2];
        }
    return f[n];
    }
    

    same idea, better for understand.


  • 0
    S
    class Solution {
    public:
        int climbStairs(int n) {
            int pre = 1,cur = 0;
            for(int i=0;i<n;++i)
            {
                int tem = pre + cur;
                pre = cur==0?1:cur;
                cur = tem;
            }
            return cur;
    
        }
    };
    

  • 0
    C

    Hi, I really like your solution, there's just one thing i don't understand. Here you assign mem[0] = 1; mem[1] = 2
    How come mem[0]=1? I though if the stair number is 0, there should be 0 way to climb 0 step. And if the stair number is 1, there should be only one way, because we can only climb one step...


Log in to reply
 

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