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

• 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).

• 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);
}  ``````

• Good one, Thanks!

• 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);
}``````

• But maybe have no better performance than the Fibonacci method.

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