解题思路

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

f(n)=f(n-1)+f(n-2),\quad n\ge 2

P3835.1+2问题

1000ms

Difficulty: 3

算法与标签>动态规划

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

记答案为 $f(n)$

输入

预期输出（选填）