【leetcode】70-ClimbingStairs

problem

ClimbingStairs

题意：

爬台阶问题，每次可以爬１个或者两个台阶，问如果有n个台阶，可以有多少种方法爬到顶部？

解析：

对于n=1,有一种方法；n=2，有两种方法；

对于n>2，对于每一个台阶i到达顶端，最后一步都有两种方式，从i-1再爬一步，或者从i-2再爬２步。

即也就是说到达台阶i的方法数=达台阶i-1的方法数+达台阶i-2的方法数。所以该问题是个DP问题，

也可以使用Fibonacci Number。

code

class Solution {

public:

    int climbStairs(int n) {

        //f[n] = f[n-1] + f[n-2];

        int fn, fnm1, fnm2;

        if(n==) return ;

        if(n==)  return ;

        fnm2 = ;

        fnm1 = ;

        for(int i=; i<=n; i++)

        {

            fn = fnm1 + fnm2;

            fnm2 = fnm1;

            fnm1 = fn;

        }

        return fn;

    }

};

参考

1.leetcode_ClimbingStairs;

2. solution;

完