6663: DP1 斐波那契数列
[Creator : ]
Description
大家都知道斐波那契数列，现在要求输入一个正整数 $n$，请你输出斐波那契数列的第 $n$ 项。
斐波那契数列是一个满足
$fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right\}$ 的数列。
斐波那契数列是一个满足
$fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right\}$ 的数列。
Input
仅输入一个正整数 $n$。
Output
输出斐波那契数列中第 $n$ 个数。
Constraints
$1\leq n \leq 100$
Sample 1 Input
4
Sample 1 Output
3
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。
Sample 2 Input
1
Sample 2 Output
1
Sample 3 Input
2
Sample 3 Output
1
HINT
相同题目：牛客网。