这道题参考了这个网址: http://blog.csdn.net/u012490475/article/details/48845683
/*
首先考虑边界情况，当有1层时，有一种方法。
然后再看2层时，有1+1、和2+0，两种方法。
再看3层时，首先有两种选择：走一步或者走两步。
如果走两步，那后面还剩一步可走；
如果走一步，后面还剩两步可走，后面的方法即可等同于上面的2层情况。
即可归纳出用C(i) = j; 表示n层时有j种可能。
C(1) = 1;
C(2) = 2;
C(3) = C(3-2) + C(3-1); //因为只有两种选择.
C(4) = C(4-2) + C(4-1);
…
C(n) = C(n-2) + C(n-1);
*/
public int climbStairs(int n) {
int a = 1;
int b = 1;
int c = 1;
for(int i = 1; i < n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
上面的是iteration的做法，下面是递归，非常简洁。
public static int climbStairs(int n) {
// write your code here
if (n == 1) return 1;
else if (n == 2) return 2;
else return climbStairs(n - 1) + climbStairs(n - 2);
}
另外看到Python的解法，更为简洁精妙
/*
经典的动态规划问题。每次上一个台阶或者两个台阶，问一共有多少种方法到楼顶。这个实际上就是斐波那契数列的求解。可以逆向来分析问题，如果有n个台阶，那么走完n个台阶的方式有f(n)种。而走完n个台阶有两种方法，先走完n-2个台阶，然后跨2个台阶；先走完n-1个台阶，然后跨1个台阶。所以f(n) = f(n-1) + f(n-2)。
*/
Ref: http://bookshadow.com/weblog/2015/08/23/leetcode-climbing-stairs/