My Solution, is there any better solution?


  • 0
    S
    class Solution {
    public:
        int climbStairs(int n) {
            if (aux[n] == 0) {
                if (n == 0 || n == 1) aux[n] = 1;
                else aux[n] = climbStairs(n-1) + climbStairs(n-2);
            }
            return aux[n];
        }
    private:
        int aux[10000] = {0};
    };

  • 1
    B

    Well one improvement is to make it constant memory. You dont need to store all 'n' solutions in aux.
    You just need to remember the last two.


  • 0
    D

    I think you can change the recursively call. below is my python solution.

    class Solution:
        # @param n, an integer
        # @return an integer
        def climbStairs(self, n):
            if n < 2:
                return 1
            ways = [0] * (n+1)
            ways[0] = 0
            ways[1] = 1
            ways[2] = 2
            for i in range(3, n+1):
                ways[i] = ways[i-2] + ways[i-1]
            return ways[n]

  • 0
    D
    This post is deleted!

  • 0
    D

    I have other idea we can use constant memory like upload guy said. below is my new solution.after modify.

    class Solution:
        # @param n, an integer
        # @return an integer
        def climbStairs(self, n):
            if n == 1:
                return 1
            if n == 2:
                return 2
    
            first   = 1
            second  = 2
            for i in range(n-2):
                first, second = second, second + first
    
            return second

  • 0
    R
    class Solution {
    public:
        int climbStairs(int n) {
            if(n<=0)return 0;
            if(n==1)return 1;
            if(n==2)return 2;
           int result[3];
           
           result[0]=0;
           result[1]=1;
           result[2]=2;
         
          for(int i=3;i<=n;i++){
              result[i%3]=result[(i-1)%3]+result[(i-2)%3];
          }
          return result[n%3];
        }
    };

Log in to reply
 

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