Climbing Stairs

=====================

Problem Statement

You are climbing a staircase that has

n

stairs. At each step, you can either climb 1 or 2 stairs. Determine the total number of distinct ways to climb to the top of the staircase.

Rules and Constraints

The staircase has
n
stairs.
At each step, you can either climb 1 or 2 stairs.
You must reach the top of the staircase.
You are not allowed to climb more than 2 stairs at a time.

Time and Space Complexity

The algorithm should have a time complexity of O(n) and a space complexity of O(n) (due to the recursion stack). Alternatively, an iterative solution with a space complexity of O(1) is also acceptable.

Notes

No additional notes or assumptions are provided. You should use the given constraints and rules to determine the final answer.

Example

Input: {"input_data":[1,2,3]} Output: [1,2,3]