Why this is wrong? Time limit...


  • 0
    E

    class Solution {
    public:
    int total=0;
    int climbStairs(int n) {
    if(n==0)

                total++;
            
            if(n==1)
            
                 total=climbStairs(n-1);
            
            if(n>1)
            {
                total=climbStairs(n-1);
                total=climbStairs(n-2);
            }
        return total;
    }
    

    };


  • 1
    C

    Because they're too much unnecessary calculate

    You should cache every result

    Otherwise you should avoid recursion


  • 0
    C

    @eilloon yeah.. Try dynamic programing.

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

Log in to reply
 

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