解题思路

本题为典型的动态规划：设 $f(n)$ 为用 1 或 2 的若干个数按顺序恰好凑成 $n$ 的方案数。 最后一步若取 1，则前面需凑出 $n-1$；若取 2，则前面需凑出 $n-2$。因此有

题面描述

给定一个非负整数 $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$