直接说“爬楼梯”问题其实就是“斐波那契数列”问题,我反正是无法理解的。所以本文将详细解释“爬楼梯”问题是怎么转换为“斐波那契数列”问题的。
爬楼梯
还是斐波那契数列问题
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
为什么这么说是斐波那契数列问题?举个例子。假设F(n)为爬n层楼梯的方法数。
- 假设爬0层楼梯
- 只有一种方案,F(0)=1
- 假设爬1层楼梯
- 只能爬一层,还是只有一种方法。F(1)=1
- 假设爬2层楼梯
- 先爬一层,再爬一层
- 直接爬两层,共两种方案。F(2)=2
- 假设爬3层楼梯
- 先爬一层,剩下2层没爬。而爬剩下这两层的方法数那不就是F(2)吗?
- 先爬两层,剩下1层没爬。那剩下这一层的方法数不就是F(1)吗?
- 先爬一层或先爬两层的方法数总和就是F(3),即F(2)+F(1)=F(3)
- 假设爬4层楼梯
- 先爬一层,剩下3层没爬。爬剩下这3层的方法数就是F(3)
- 先爬两层,剩下2层没爬。爬剩下这2层的方法数就是F(2)
- …
- 假设爬n层楼梯
- 先爬一层,剩下n-1层没爬。爬剩下这n-1层的方法数就是F(n-1)
- 先爬两层,剩下n-2层没爬。爬剩下这n-2层的方法数就是F(n-2)
那么最后F(n)就等于“先爬一层”和“先爬两层”的方法数总和
F(n)=F(n-1)+F(n-2)
可以看到计算“爬楼梯”方法数也是一个递归的过程,而且和求斐波那契数列几乎是一模一样,都是从求F(n)开始分割出多个子问题,然后对每个子问题求解。
代码实现
C++代码
当然它首先是递归问题,然后才是动态规划问题。那么递归,记忆性搜索和动态规划都是可以解决这个问题的。这里就只放动态规划的C++代码吧。
需要注意的是,爬第0层也算一种方案,所以f(0)=1。而斐波那契数列的f(0)=0
#include<iostream>
#include<vector>
using namespace std;
int fib(int n)
{
if(n<=1)
{
return 1;
}
int left=0,right=1;
int result=0;
for(int i=1;i<=n;i++)
{
result=left+right;
left=right;
right=result;
}
return result;
}
int main()
{
while(true)
{
int n;
cin>>n;
cout<<fib(n)<<endl;
}
}