Frog Ladder Jumper

A frog is trying to climb a ladder with n steps. The frog can jump either 1 or 2 steps at a time. Your task is to determine the number of distinct ways in which the frog can reach the top (step n).

The recurrence relation for this problem is given by:

[ dp[i] = dp[i-1] + dp[i-2], \quad i \ge 2 ]

with the base cases defined as:

[ dp[0] = 1, \quad dp[1] = 1 ]

For example, when n = 4, the frog has 5 different ways to reach the top. Solve the problem using an iterative dynamic programming approach.

inputFormat

The input consists of a single integer n (0 ≤ n ≤ 10^4) representing the number of steps in the ladder.

outputFormat

Output a single integer which is the number of distinct ways the frog can reach the top.

0

1