Leetcode:climbing_stairs

Leetcode:climbing_stairs

一、 題目

爬樓梯，一共有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);
    }
};