public int climbStairs(int n) {
if(n==0)
return 0;
if(n==1)
return 1;
if(n==2)
return 2;
int a = 1;
int b = 2;
int sum = 0;
for(int i=2;i<n;i++){
sum = a+b;
a = b;
b = sum;
}
return sum;
}
根据题目意思可以得到，每一阶都有1或者2两种走法，那么例如n=5的时候，最后一步可以从第4阶走一步上去，或者从第3阶走两步上去，然后再分析子问题易得f(n=5)即为f(n=4)+f(n=3)，不用担心这两个子问题会有解法重复的问题，因为他们最后一步肯定是不同的。
到此可以简化问题成一个斐波那契数组，但是直接用递归的方法求解时会有超时的问题，所以采用如上的方法求解递归。
网友评论