My divide and conquer way to solve this problem(Java)


  • 8

    Hi guys, here is my solution:

    public class Solution {
        public int climbStairs(int n) {
            //bottom case
            if(n < 1){
                return 0;
            }
            
            if(n == 1){
                return 1;
            }
            if(n == 2){
                return 2;
            }
            if(n == 3){
                return 3;
            }
            
            return climbStairs(n/2)*climbStairs(n - n/2) + climbStairs(n/2 - 1) * climbStairs(n - n/2 - 1);
            
        }
    }
    

    Each time we cut n stairs in the middle:

    total case(n) = total case(head half of n) * total case(tail half of n) + additional case.

    About the additional case: The border on head half and tail half contribute an '1', then we form a '2' in the middle. So total case of additional case should = total case(head half - 1) * total case(tail half -1).


  • 0
    Y

    Intresting, this is my concise solution.

    int climbStairs(int n) {
        if (n <= 3) return n;
        int mid = n >> 1;
        int left = n - mid;
        return climbStairs(mid) * climbStairs(left) + climbStairs(mid - 1) * climbStairs(left - 1);
    }  

  • 0

    Good one, Thanks!


  • 0
    V

    we have same idea, divide and conquer+combination math:

    int climbStairs(int n) {
        if(n==0)
            return 1;
        if(n==1)
            return 1;
        return climbStairs(n/2)*climbStairs((n+1)/2)+climbStairs((n-2)/2)*climbStairs((n-1)/2);
    }

  • 0
    V

    But maybe have no better performance than the Fibonacci method.


Log in to reply
 

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