解题思路

• 本题要求用若干个数 1、2、3 相加，按顺序恰好得到 $n$ 的方案数，顺序不同视为不同方案（如 $1+2$ 与 $2+1$ 不同）。

• 设 $f(n)$ 为答案，考虑最后一步取值：

  • 若最后取 1，则前面需凑成 $n-1$，方案数为 $f(n-1)$；
  • 若最后取 2，则前面需凑成 $n-2$，方案数为 $f(n-2)$；
  • 若最后取 3，则前面需凑成 $n-3$，方案数为 $f(n-3)$。

• 因此得到动态规划递推式（“三项斐波那契”）：

题面描述

本题在“每次取 1 或 2 凑成 $n$”的基础上做进一步扩展，给定一个非负整数 $n$。每次可取数 1、2 或 3，将若干个数相加恰好得到 $n$。两种方案只要在某个位置取的数不同，就视为不同（即顺序有区分）。求不同方案数。

记答案为 $f(n)$。

输入格式

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

输出格式

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

数据范围

• $0 \le n \le 60$

样例

样例输入

4

样例输出

7

说明

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

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