现在的位置: 首页 > 编程语言 > 正文

Leetcode:climbing_stairs

2019年11月04日 编程语言 ⁄ 共 273字 ⁄ 字号 暂无评论

一、 题目

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

给我留言

留言无头像?