首页 > 代码库 > 跳台阶问题
跳台阶问题
给定一个有N个台阶的楼梯，一个人从下到上开始跳台阶，这个人有两种跳的方式：一次跳一个台阶，一次跳两个台阶；
问：从台阶底端跳到台阶顶端，有多少种跳台阶的方式？
解法一：递归法
分析：
首先我们考虑最简单的情况。如果只有1个台阶，那么显然只有一种跳法；如果是2级台阶，那么有2种跳法。对于一个有n级台阶的楼梯来说，我们设跳法为 f(n) ，假如我们先跳1个台阶，则剩下有 n-1 个台阶，跳法为 f(n-1) 次，假如我们先跳2个台阶，则剩下 n-2 阶，跳法为 f(n-2)；由此可以推出，对于一个n阶的楼梯，有以下这个跳台阶的公式：
long long Fibonacci(unsigned int n) { if(n==1) return 1; if(n==2) return 2; return Fibonacci(n-2)+Fibonacci(n-1); }
解法二：递推法（使用递归法有很多重复计算，事实上我们可以从后往前推，一步步利用之前计算的结果递推，初始化时a=b=1,然后递推计算最后，b的值为最后的值）
long long Fibonacci1(unsigned int n) { if(n<2) return 1; int a=1,b=1; int temp; for(int i=2;i<=n;i++) { temp=a+b; a=b; b=temp; } return b; }
更清楚代码为：
long long Fibonacci1(unsigned int n) { if(n<2) return 1; int dp[3]={1,1}; for(int i=2;i<=n;i++) { dp[2]=dp[0]+dp[1]; dp[0]=dp[1]; dp[1]=dp[2]; } return dp[2]; }
跳台阶问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。