P4723 爬行路线（基础）

解题思路

第一步：看懂题目。 一只小蜜蜂在数字蜂房上爬，只能从标号小的蜂房爬到相邻且标号大的蜂房，问从 M 号蜂房爬到 N 号蜂房有多少种路线。

第二步：找到关键规律。 蜂房是一个六边形拼成的图案，每个蜂房和它相邻的蜂房标号刚好差 1 和差 2。也就是说，站在标号为 k 的蜂房，下一步只能到 k+1 或 k+2 号蜂房。这就是这道题最关键的地方！

第三步：把问题转化成熟悉的“上楼梯”问题。 知道了这个规律，问题就变成：从 1 开始，每次可以走 1 步或 2 步，问到达 N-M+1 有多少种走法。设 f[i] 表示从 1 到 i 的路线数，那么要到达 i，上一步只可能来自 i-1 或 i-2，所以 f[i] = f[i-1] + f[i-2]。这正好是斐波那契数列的递推式！f[1]=1，f[2]=1，之后每一项都等于前两项之和。

第四步：为什么是从 1 到 N-M+1 而不是 M 到 N？ 因为蜂房的规律每两个标号重复一次，从 M 到 N 的走法和从 1 到 N-M+1 的走法是一一对应的，路线数相同。比如样例从 1 到 14，N-M+1=14，f[14]=377，正好等于样例输出。

第五步：再理解一下蜂房为什么这样编号。 第一行只有 1 号蜂房，第二行是 2、3 号，第三行是 4、5 号，第四行是 6、7 号……按照这种蛇形排列，每个蜂房向左下方和右下方伸出的两个蜂房，恰好就是它自己的编号加 1 和加 2。所以从任意一个蜂房出发，下一步只有两种选择，这正对应了斐波那契数列“要么跳 1 格、要么跳 2 格”的经典模型，就像上楼梯时一次可以跨一级或两级台阶一样。如果还是不放心，可以自己按规律画一画小蜂房，数一数从 1 到 5、从 1 到 6 的路线数，会发现确实分别是 5 和 8，正是斐波那契数列。

第六步：注意边界与数据大小。 如果 M 和 N 只差 1，也就是两个相邻蜂房，那么只有直接爬过去这一种路线，此时 N-M+1=2，f[2]=1，结果正确。题目保证 M<N，且 N-M 最大是 90，最多需要算到 f[91]。斐波那契数列第 91 项大约是 4.6×10^18，用 long long（64 位整数）存储刚好放得下。

参考代码

// 蜜蜂爬行路线：从M爬到N，方案数等于斐波那契数列第(N-M+1)项
#include <iostream>
using namespace std;
int main() {
    int from, to;
    cin >> from >> to;
    int target = to - from + 1; // 需要求斐波那契第 target 项
    long long fib[100];
    fib[1] = 1; fib[2] = 1;
    for (int i = 3; i <= target; i++)
        fib[i] = fib[i-1] + fib[i-2];
    cout << fib[target] << endl;
    return 0;
}

复杂度分析

只需要从 3 递推到 target，target 最大是 91，所以时间复杂度是 O(N-M)，最多 91 次加法，非常快。空间上用一个长度 100 的 long long 数组，空间复杂度也是 O(N-M) 量级，几乎可以忽略不计。