One tricky way to do it with recursion in C++ (0ms, no extra space)


  • 0
    N

    Intuitive recursion approach like "return climbStairs(n -1) + climbStairs(n - 2);" would surely cost too much and lead to TLE. Thus more work are needed when dividing the scale of problem. I cut n into half and then add three situations together. Here's AC code.

    class Solution {
    public:
        int climbStairs(int n) {
            if(n == 0)  return 1;
            if(n == 1 || n == 2)    return n;
            
            int a = climbStairs(n / 2); 
            int b = climbStairs((n - 1) / 2 - 1); 
            int c = climbStairs(n / 2 - 1);
            int d = climbStairs((n -1) / 2);
            
            return b * a + d * a + d * c;
        }
    };
    

Log in to reply
 

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