蜜蜂路线

题意

蜜蜂只能从编号小的蜂房走到编号大的相邻蜂房。给定 m < n，求从 m 到 n 的路线数。

思路

这个蜂房路线模型的递推与斐波那契数相同。

设距离 d = n - m。从起点到终点的路线数满足：

text

1
2
3ways[0] = 1
ways[1] = 1
ways[d] = ways[d-1] + ways[d-2]

因此答案是斐波那契式递推的第 d 项。

小 DP 表

d	0	1	2	3	4	5
ways[d]	1	1	2	3	5	8

样例 1 -> 14，距离为 13，答案为 377。

Python 知识

Python 大整数可以直接处理路线数。
previous, current = current, previous + current 是滚动递推常用写法。
map(int, input().split()) 读取一行两个整数。

参考笔记：

/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md

代码

python

1
2
3
4
5
6
7
8
9m, n = map(int, input().split())
distance = n - m

previous = 1
current = 1
for _ in range(distance):
    previous, current = current, previous + current

print(previous)

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */
#include <bits/stdc++.h>
using namespace std;

int m, n;
char a[300], b[300], c[300];

void add(char *res, char *x, char *y) {
    int lenx = strlen(x), leny = strlen(y);
    int carry = 0, k = 0, i = lenx - 1, j = leny - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += x[i--] - '0';
        if (j >= 0) sum += y[j--] - '0';
        carry = sum / 10;
        res[k++] = sum % 10 + '0';
    }
    res[k] = '\0';
    reverse(res, res + k);
}

int main() {
    cin >> m >> n;
    int d = n - m;
    strcpy(a, "1");
    strcpy(b, "1");
    for (int i = 0; i < d; i++) {
        add(c, a, b);
        strcpy(a, b);
        strcpy(b, c);
    }
    cout << a << endl;
    return 0;
}

Pythonic 写法

滚动递推：

python

1
2
3
4
5m, n = map(int, input().split())
a = b = 1
for _ in range(n - m):
    a, b = b, a + b
print(a)

复杂度

时间复杂度为 $O(n-m)$ ，空间复杂度为 $O(1)$ 。

总结

本题和数楼梯一样，是斐波那契递推模型；区别只是把“台阶距离”换成了“蜂房编号差”。

目录

题意

思路

小 DP 表

Python 知识

代码

Pythonic 写法

复杂度

总结