# 1. Introduction

This blog post delves into a classic problem often encountered in dynamic programming and combinatorics - the "Climbing Stairs" problem. It's a problem that models a situation where one needs to determine the number of distinct ways to reach the top of a staircase, given that each step can either be 1 or 2 steps at a time.

## Problem

Given a staircase with *n* steps, the task is to find out how many distinct ways there are to climb to the top. At each step, you can choose to climb either 1 step or 2 steps.

# 2. Solution Steps

1. Recognize that this is a Fibonacci sequence problem, where the number of ways to reach the nth step is the sum of ways to reach the (n-1)th step and the (n-2)th step.

2. Use dynamic programming to build up the solution from the base cases.

3. Initialize an array *dp* with a size of *n + 1*.

4. Set the base cases: *dp[1] = 1* and *dp[2] = 2*.

5. Iterate from 3 to n, calculating *dp[i]* as *dp[i-1] + dp[i-2]*.

6. Return *dp[n]*, which represents the number of ways to reach the top.

# 3. Code Program

```
public class ClimbingStairs {
public static void main(String[] args) {
int n = 5;
System.out.println(climbStairs(n)); // Test the function
}
// Function to calculate the number of ways to climb stairs
public static int climbStairs(int n) {
if (n == 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
```

### Output:

8

### Explanation:

1. *climbStairs*: This function calculates the number of ways to climb to the top of a staircase with *n* steps.

2. It handles the base case where *n* is 1. In this case, there's only one way to climb.

3. The function initializes a dynamic programming array *dp*, where *dp[i]* represents the number of ways to reach step *i*.

4. It sets the base cases for *dp[1]* and *dp[2]*.

5. The function then iteratively computes the values of *dp[i]* for *i* from 3 to *n* using the relation *dp[i] = dp[i - 1] + dp[i - 2]*. This relation follows from the fact that to reach the ith step, one can come either from the (i-1)th step or the (i-2)th step.

6. The final result *dp[n]* is the total number of distinct ways to reach the top of the stairs.

7. This approach efficiently computes the result using dynamic programming to avoid redundant calculations.

## Comments

## Post a Comment