规则简述：给定一个正整数n表示楼梯总台阶数，你一次可以走1或者2，设计算法求解走上n个台阶的不同走法。

 

EX：n=3

output: 3

1.  1+1+1

2.  1+2

3.  2+1

斐波那契求解：

class Solution {public:    int climbStairs(int n)     {        vector
     
       feb(n+1,0);        if(n==0)            return 0;        if(n==1)            return 1;        feb[0]=1;        feb[1]=1;        for(int i=2;i<=n;i++)            feb[i]=feb[i-1]+feb[i-2];        return feb[n];    }};
     

核心思想：

F(n)=F(n-1)+F(n-2)

对于不同的n，方法数构成数列恰好为斐波那契数列。