首页 > 代码库 > 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); } };
Leetcode:climbing_stairs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。