Climbing Stairs - Python Solution

1. Introduction

The "Climbing Stairs" problem is a classic example of dynamic programming and combinatorics. It's a fundamental question in algorithm design, often used to introduce the concept of solving problems through recursion and memoization. The problem simulates a scenario where one climbs stairs with the option to take either one or two steps at a time, aiming to count all possible distinct ways to reach the top.

Problem

Given a staircase with n steps, each time you can either climb 1 or 2 steps. The task is to determine the number of distinct ways you can climb to the top of the staircase.

2. Solution Steps

1. Recognize the problem as a Fibonacci sequence, where the number of ways to reach step n is the sum of ways to reach step n-1 and n-2.

2. Use dynamic programming to avoid redundant calculations.

3. Initialize an array to store the number of ways to reach each step.

4. The base cases are: 1 way to reach step 0 (no steps), and 1 way to reach step 1.

5. Iterate from step 2 to n, calculating the number of ways to reach each step.

6. Return the number of ways to reach step n.

3. Code Program

def climbStairs(n):
    if n <= 1:
        return 1

    ways = [0] * (n + 1)
    ways[0], ways[1] = 1, 1

    for i in range(2, n + 1):
        ways[i] = ways[i - 1] + ways[i - 2]

    return ways[n]

# Example Usage
print(climbStairs(2))
print(climbStairs(3))

Output:

2
3

Explanation:

1. Dynamic Programming Approach: The problem is solved using dynamic programming to efficiently calculate the number of ways to reach each step.

2. Base Cases: The base cases handle the scenario of having no steps (0) and one step (1).

3. Iterative Solution: The function iteratively computes the number of ways for each step from 2 to n.

4. Fibonacci Sequence: Each step's number of ways is the sum of the two previous steps, forming a Fibonacci sequence.

5. Result: The function returns the total number of distinct ways to reach the top of the staircase.