吃糖果

题目描述

名名有 $N$ 块巧克力（ $0 < N < 20$ ），每天可以吃 $1$ 块或 $2$ 块。问有多少种不同的吃完方案。

输入格式

输入一行，整数 $N$ 。

输出格式

输出一行，方案数。

样例输入

text

样例输出

text

思路

设 $f[i]$ 为吃完 $i$ 块的方案数。最后一天吃 $1$ 块则前面有 $f[i-1]$ 种方案，吃 $2$ 块则有 $f[i-2]$ 种，于是 $f[i] = f[i-1] + f[i-2]$ ，初始 $f[0] = f[1] = 1$ 。用两个变量滚动递推即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/usr/bin/env python3
# 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-09-29 22:52
# update_at: 2026-09-29 22:52

import sys


def solve() -> None:
    n: int = int(sys.stdin.buffer.read())
    a = b = 1  # f[0] = f[1] = 1
    for _ in range(2, n + 1):
        a, b = b, a + b  # 滚动到 f[i]
    print(b)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-05 05:11
 * update_at: 2026-10-05 05:11
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll n;          // 巧克力总数
ll a = 1, b = 1; // a=f[i-2], b=f[i-1]，初始 f[0]=f[1]=1

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    // 滚动递推：f[i] = f[i-1] + f[i-2]
    for (ll i = 2; i <= n; i++) {
        ll c = a + b; // c 为 f[i]
        a = b;
        b = c;
    }

    cout << b << "\n";
    return 0;
}

目录