学步园

一、     题目

   爬楼梯，一共有n阶，每次可以跨1阶或2阶，则爬到顶部一共有多少种爬法?

二、     分析

   设f(n)表示爬n阶楼梯的不同种方法数，为了爬到第n阶处，有两种选择:

  1.     从n-1阶前进一步

  2.     从n-2阶前进两步

因此有，f(n)=f(n-1)+f(n-2)     这不就是斐波那契数列吗？

故有，

   方法1:迭代

   方法2:递归

   方法3:公式法    F(n)=(1/√5)*{[(1+√5)/2]^n -[(1-√5)/2]^n}

class Solution {
public:
    int climbStairs(int n) {
        int flag;
    	int stair0=1;
    	int stair1=1;
    	if(n<=0)
        	return 0;
        if(n==1)
        	return 1;	
        for(int i=2;i<=n;i++) {
        	flag=stair1;
        	stair1=stair0+stair1;
        	stair0=flag;
        }
        return stair1;
    }
};

公式法:
class Solution {
public:
    int climbStairs(int n) {
        double flag=sqrt(5);
        return floor((pow((1+flag)/2,n+1)+pow((1-flag)/2,n+1))/flag+0.5);
    }
};