首页 > 代码库 > [LeetCode OJ]-Climbing Stairs
[LeetCode OJ]-Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
一共有n阶楼梯，每次只能爬1阶或2阶，问爬到顶端一共有多少种方法
方法一：
利用二叉树的思想，对于n=3时有3种方法，有几个叶子节点便有几种方法
1 void climb( int remainder, int &way) 2 { 3 if(remainder==0 || remainder==1) 4 { 5 way++; 6 return; 7 } 8 9 climb(remainder-1, way);10 climb(remainder-2, way);11 return;12 }13 14 class Solution {15 public:16 int climbStairs(int n) {17 int result=0;18 climb(n, result);19 return result;20 }21 };
但是这种方法对于n比较大时会超时，在测试用例中对于n=38就会TLE（Time Limit Exceed）。
方法二：
总结规律，通过以下数据，我们发现
way(1)=1
way(n) = way(n-1) + Fibonacci(n-1) n=2,3,4,5,6,....
1 class Solution { 2 public: 3 int climbStairs(int n) { 4 int result=1; 5 int Fibonacci_0=0, Fibonacci_1=1, temp; 6 for(int i=1; i<n; i++) 7 { 8 result += Fibonacci_1; 9 temp = Fibonacci_1;10 Fibonacci_1 = Fibonacci_0 + Fibonacci_1;11 Fibonacci_0 = temp;12 13 }14 return result;15 }16 };
对于leetcode中所有的测试数据都可以通过
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。