---
title: "吃糖果"
created: 2025-11-28
tags:
  - 算法
---

# 吃糖果

## 题目 [吃糖果](https://www.acwing.com/problem/content/description/3436/)

![[image-6dc23860.png]]

## 思路分析

斐波那契数列的一个应用。对于给定的N块巧克力，名名可以选择在第一天吃1块或2块，剩下的巧克力可以按照同样的方式继续选择。因此，如果我们将吃掉N块巧克力的方案数定义为`F(N)`，那么可以得到：

- 当`N = 1`时，有`F(1) = 1`种方案。
- 当`N = 2`时，有`F(2) = 2`种方案（第一天吃1块，第二天吃1块；或者第一天吃2块）。
- 对于`N > 2`，名名第一天有两种选择：
- 如果第一天吃1块，剩下`N-1`块，有`F(N-1)`种方案。
- 如果第一天吃2块，剩下`N-2`块，有`F(N-2)`种方案。

因此，对于`N > 2`，有`F(N) = F(N-1) + F(N-2)`。

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 1001;

int fn[N];

int n;

int main() {

    cin >> n;

    fn[1] = 1;

    fn[2] = 2;

    for(int i = 3; i <= n; i++)

        fn[i] = fn[i-1] + fn[i-2];

    cout << fn[n] << endl;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

int n;

int main()

{

    cin>>n;

    int a,b,fn;

    a=1,b=2;

    for(int i=1;i<=n;i++){

        if(i==n)

            cout<<a<<endl;

        fn=a+b;

        a=b,b=fn;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[递归与递推模型|递归与递推模型]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/递归与递推模型/递推/圆圈中最后剩下的数字|圆圈中最后剩下的数字]]