首页 > 代码库 > [LeetCode] Climbing Stairs
[LeetCode] 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?
如果用递归的方法，就容易出现Time Limit Exceeded！
说明：本算法用了动态规划的相关知识。由于递归算法会产生低效的程序，有时我们需要把递归算法写成非递归算法，利用把子问题的答案系统的记录在一个表内，
，利用这种技巧的方法就称为动态规划。
我们知道的利用动态规划的例子如：计算斐波那契数列。
计算斐波那契数列的自然递归程序有很多重复的计算，非常低效，用动态规划计算Fn就可以先把Fn-1和Fn-2记录起来直接用。
以下用递归的方法，结果是对的，时间超时了，感受一下：
class Solution {public: int climbStairs(int n) { if(n==1) return 1; int num2 = n/2; int sum = 0; int step1; for(int step2=0;step2<=num2;step2++)//共走了step2个2步 { step1 = n - 2*step2; sum += summary(step1,step2+1); } return sum; }private: int summary(int n,int m)//n个苹果放到m个篮子里有几种放法？ { if(m==1 || n==0) return 1; int sum=0; for(int i=0;i<=n;i++)//第1个篮子放i个苹果 { int m1 = summary(n-i,m-1); sum+=m1; } return sum; }};
深挖内在联系，"走n步" = "前面n-1步的基础上再走1步" + "n-2步的基础上再走2步",看下面的编码，不用将每一步的结果存到vector<int>里面，那样还要占额外内存：
class Solution {public: int climbStairs(int n) { if(n==1 || n==2) return n; int PrePreStep = 1;//n=1 int PreStep = 2;//n=2 int res = 0; for(int i=3;i<=n;i++) { res = PrePreStep + PreStep; PrePreStep = PreStep; PreStep = res; } return res; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。