楼梯问题之递推

长沙7喜 2019-10-19

展开全文

建议大家在浏览这篇文章之前，先来回顾一下昨天的文章。（楼梯问题之递推）

今天要为大家介绍一种更为高效的递推算法。

核心算法

递推，斐波那契数列。

问题描述

爬楼梯问题，每次可以走1步或者2步，爬上n层楼梯的总方法。

递推思路

思考一下这样一个问题，现在一共有5层楼梯每次可以爬1或2层楼梯。那么达到第5层可以从第几层直接爬到呢？答案是第3层或第4层。那么第4层呢，又从2和3层来的；第3层呢，从1层或2层爬上来；至于第2层呢，从地面或1层可以爬到，故答案为2；第一层呢，就只剩下1种方式了。

简单的说第五层5来自于3层和4层,4层来自于2层和3层，以此类推。

于是我们就得到了一个数列1,2,3,5,8。
如果再首项加上1变成：1,1,2,3,5,8。我们就得到了斐波那契数列。正好我们可以把首项下标设为0，于是第i项就是爬到i层楼梯的方案了。

递推图解

代码

#include<cstdio>
long long a[5005],n;
int main() {
    scanf('%lld',&n);
    a[0] = 1;
    a[1] = 1;
    for(int i = 2; i <= n; i++) {
        a[i] = a[i-1]+a[i-2];
    }
    printf('%lld\n',a[n]);
    return 0;
}

分析

（本栏内容与楼梯问题无关。）
这样的代码复杂度为O(N)。就算n很大也可以快速求解。但还是无法通过给出的例题，原因是答案的数据很大，就算是long long也无法给出正确答案。这时我们需要写出高精度。给出高精度代码。

代码

#include<cstdio>
#include<algorithm>
#define MAX 5005
using namespace std;
int n;
struct big_int {
   int num[MAX];
   int len;
   big_int() {
       for(int i = 0; i < MAX; i++) {
           num[i] = 0;
       }
       len = 0;
   }
   void clear() {
       for(int i = 0; i < MAX; i++) {
           num[i] = 0;
       }
       len = 0;
   }
}a,b,c;
void evaluation(big_int x,big_int &y) {
   y.len = x.len;
   for(int i = 0; i <= x.len; i++) {
       y.num[i] = x.num[i];
   }
   return;
}
void out(big_int x) {
   for(int i = c.len; i >= 0; i--) {
       putchar(x.num[i]+'0');
   }
   putchar('\n');
   return;
}
int main() {
    scanf('%d',&n);
    if(n == 0) {
       puts('0');
       return 0;
   }
    a.num[0] = 1;
    b.num[0] = 1;
    for(int i = 2; i <= n; i++) {
       c.clear();
       c.len = max(a.len,b.len);
        for(int i = 0; i <= c.len; i++) {
           c.num[i] += a.num[i]+b.num[i];
           if(c.num[i] > 9) {
               c.num[i+1] = c.num[i]/10;
               c.num[i] = c.num[i]%10;
           }
       }
       while(c.num[c.len+1] > 0) {
           c.len++;
       }
       evaluation(a,b);
       evaluation(c,a);
    }
    out(a);
    return 0;
}