题面描述

给定一个非负整数 $n$。每次可取数 1 或 2，将若干个数相加恰好得到 $n$。两种方案只要在某个位置取的数不同，就视为不同（即顺序有区分）。求不同方案数。

记答案为 $f(n)$

输入格式

• 第一行一个整数 $n$。

输出格式

• 输出一行一个整数：$f(n)$。

数据范围

• $0 \le n \le 60$

样例

样例输入

4

样例输出

5

说明

• 对于 $n=4$，所有顺序不同的分解（每次只能取 1 或 2）共有 5 种，分别是：

1. $1+1+1+1$
2. $1+1+2$
3. $1+2+1$
4. $2+1+1$
5. $2+2$

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写