爬楼梯:动态规划

另一种“斐波那契数列”

直接说“爬楼梯”问题其实就是“斐波那契数列”问题,我反正是无法理解的。所以本文将详细解释“爬楼梯”问题是怎么转换为“斐波那契数列”问题的。

爬楼梯

还是斐波那契数列问题

假设你正在爬楼梯。需要 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;
    }
}
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x