Unique Ways to Climb Stairs

You are given a staircase with N steps. At each step, you can decide to climb either 1 step or 2 steps.

The task is to compute the number of unique ways to reach the top of the staircase. The recurrence relation for the number of ways is given by: $$dp(n)=dp(n-1)+dp(n-2)$$ for \( n \ge 3 \), with base cases \( dp(1)=1 \) and \( dp(2)=2 \).

This is a classic dynamic programming problem which can be solved efficiently using an iterative approach.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 50) representing the number of steps in the staircase.

outputFormat

Output a single integer representing the number of distinct ways to climb to the top of the staircase.

1

1