解题思路

蜜蜂从蜂房 M 爬到蜂房 N，只能从小标号爬到大标号相邻的蜂房，问有多少种路线。

核心：这是斐波那契数列。

从蜂房 1 到蜂房 k 的路线数满足斐波那契：

• 到第 1 格：1 种
• 到第 2 格：2 种
• 到第 k 格 = 到第 k-1 格的路线数 + 到第 k-2 格的路线数

为什么？ 因为能直接爬到第 k 格的前一格只有两个（k-1 和 k-2），路线数就是两者的和。

所以从 M 到 N 的路线数 = 斐波那契第 (N-M) 项。

为什么要高精度？ N-M 最大 99，斐波那契第 99 项非常大（约 10^20），int 和 long long 都装不下，要用数组一位一位存。

举例：从 1 到 14

• 路线数 = 斐波那契第 13 项 = 377

参考代码

#include <iostream>
using namespace std;

int f[105][40];

int main() {
    int m, n;
    cin >> m >> n;

    int k = n - m;  // 斐波那契第 k 项

    f[1][0] = 1;
    f[2][0] = 2;

    for (int i = 3; i <= k; i++) {
        for (int j = 0; j < 39; j++) {
            f[i][j] += f[i - 1][j] + f[i - 2][j];  // 逐位相加
            if (f[i][j] >= 10) {  // 进位
                f[i][j + 1] += f[i][j] / 10;
                f[i][j] %= 10;
            }
        }
    }

    int p = 39;
    while (p > 0 && f[k][p] == 0) p--;
    for (int i = p; i >= 0; i--) cout << f[k][i];
    return 0;
}

复杂度分析

• 时间复杂度：O(K)，递推 K 次
• 空间复杂度：O(K)，高精度数组