LintCode 111 Climbing Stairs

这道题参考了这个网址: 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/

上一篇:TCP连接的状态与关闭方式及其对Server与Client的影响


下一篇:shell 实例