Climbing Stairs

You are a curious programmer who loves to solve puzzles. You've found yourself at the bottom of a tall staircase, and your goal is to reach the top. The challenge is to figure out all the distinct ways you can climb to the top, given certain rules. This is a classic problem that helps illustrate fundamental concepts in dynamic programming and recursion.

Problem Description

You are climbing a staircase. It takes $n$ steps to reach the top. You can climb either 1 or 2 steps at a time. Your task is to calculate the total number of distinct ways you can climb to the top.

Key Requirements:

• Determine all possible combinations of 1-step and 2-step climbs that sum up to exactly $n$.
• The order of the steps matters (e.g., 1 step then 2 steps is different from 2 steps then 1 step).

Expected Behavior:

The function should accept a non-negative integer n representing the total number of steps and return an integer representing the total number of distinct ways to reach the top.

Edge Cases:

• What happens if n is 0? (There are no steps to climb).
• What happens if n is 1? (Only one way to climb).

Examples

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Example 3:

Input: n = 1
Output: 1
Explanation: Only one way to climb: 1 step.

Example 4:

Input: n = 0
Output: 1
Explanation: If there are 0 steps, there is one "way" to reach the top (you are already there).

Constraints

• $0 \le n \le 45$
• The input n will be a non-negative integer.
• The output should be an integer.
• The solution should be efficient enough to handle the maximum value of $n$ within reasonable time limits.

Notes

• Consider the base cases carefully. How many ways are there to reach step 0 or step 1?
• Think about how the number of ways to reach step $k$ relates to the number of ways to reach previous steps.
• This problem can be solved using recursion, but be mindful of repeated calculations. Memoization or an iterative approach can improve efficiency.