1181 吃糖果
大约 3 分钟
1181 吃糖果
【算法】 递推
【C++】 数组、循环
【难度】 入门
一、题目简述
名名有 块巧克力(),每天只能吃 块或 块,每天都吃。问共有多少种不同的吃完方案。
数据范围:,答案不会超过 int 范围。
二、解题思路
2.1 分析问题
每天只有两种选择:
- 吃 块 → 剩下 块要吃
- 吃 块 → 剩下 块要吃
设 表示 块巧克力的方案数,那么:
这就是斐波那契数列的递推公式,只是初始值有所不同。
2.2 手动模拟
题目中已经给出了前几项的推导过程:
| 方案 | 方案数 | |
|---|---|---|
| 1 | 第1天吃1块 | |
| 2 | 第1天吃1块+第2天吃1块;第1天吃2块 | |
| 3 | ||
| 4 | ||
| 5 | ||
| ... | ... | ... |
可以看到,从 开始,每一项都是前两项之和。
2.3 算法选择
因为 ,数据规模非常小,直接用递推即可:
- 初始化 ,
- 从 到 ,递推
- 输出
为什么不用递归? 虽然 很小,递归也能过,但递推(循环)更直观,而且让学生体会"用小问题的答案推大问题"的递推思想。
2.4 思维拓展
本题是经典的爬楼梯问题:
有 级台阶,每次可以爬 级或 级,有多少种爬到顶的方法?
两道题的模型完全相同。理解了这道题,以后遇到类似的"每次走固定步数,求方案数"的问题,都能用递推解决。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int f[25]; // N < 20,开 25 足够
int main() {
int n;
cin >> n;
f[1] = 1; // 1 块巧克力只有 1 种吃法
f[2] = 2; // 2 块巧克力有 2 种吃法
for (int i = 3; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2]; // 递推核心
}
cout << f[n] << endl;
return 0;
}另一种写法(空间优化)
由于递推时只需要前两个状态,可以不用数组,只用三个变量轮换:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
return 0;
}
int a = 1, b = 2, c;
for (int i = 3; i <= n; i++) {
c = a + b;
a = b;
b = c;
}
// 当 n=2 时不会进入循环,直接输出 b 即可
cout << b << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,一次循环即可。
- 空间复杂度:(数组版)或 (变量轮换版)。
五、易错点
- 初始值不要搞混:,,不是标准斐波那契的 。
- 循环起点:从 开始递推,不要从 开始。
- 或 时的边界处理:数组版直接读 没问题,但变量轮换版需要特判 的情况。
六、类似题目
| 题号 | 题目 | 说明 |
|---|---|---|
| — | 斐波那契数列 | 标准版, |
| — | 爬楼梯 / 上台阶 | 模型完全相同 |
| — | 骨牌铺方格 | 方格用 骨牌铺满的方案数 |
