Dynamic ProgrammingMathFibonacci
You are climbing a staircase with n steps. Each time you may climb 1 or 2 steps. In how many distinct ways can you reach the top?
Input
A single integer n.
Output
Print the number of distinct ways.
Constraints
1 <= n <= 45
Example 1
Input
3
Output
3
1+1+1, 1+2 and 2+1: three ways.