lintcode: 爬楼梯

题目：

爬楼梯

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

样例

比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

返回 3

解题：

动态规划题目，同时还是有顺序的，把n拆成 1 、2 的组合有多少种方式，动态规划，掌握的不好，不能够灵活运行，看看这个能否自己解决。表示没有成功，，九章找的程序。。。

更新

对 n个的台阶，最后一次走，可以走一个台阶，也可以走两个台阶，则f(n) = f(n-1) + f(n-1)

初始值：f(1) = 1 f(2) = 2 f(3) = 3

这个就是费波那列数列，下面的程序就好理解了

java程序：

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n <= 1) {
            return n;
        }
        int last = 1, lastlast = 1;
        int now = 0;
        for (int i = 2; i <= n; i++) {
            now = last + lastlast;
            lastlast = last;
            last = now;
        }
        return now;
    }
}

View Code

总耗时: 1204 ms

表示不理解

这里递归程序，很好理解

Java程序：

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n == 0 || n == 1) return 1;  
        if (n < 0) return 0;  
        return climbStairs(n - 1) + climbStairs(n - 2); 
    }
}

View Code

90%测试数据的时候运行事件超时，上面博客中说了与求费波那列数列很想，然后就可以给写成非递归的程序，就和上面的一样了。下面Python程序就是根据递归的写的。所以重点还是把问题细化，分化求解。

Python程序：

class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def climbStairs(self, n):
        # write your code here
        if n==0 or n==1:
            return 1
        if n< 0:
            return 0
        f0 = 1 
        f1 = 1 
        i = 2
        while i<= n:
            f = f0 + f1
            f0 = f1
            f1 = f
            i += 1 
        return f

View Code

总耗时: 423 ms