# Problem: Climbing Stairs

## Problem Statement

[NOTE]
You are climbing a staircase. It takes `n` steps to reach the top. Each time you can either climb 1 or 2 steps. The task is to find the number of distinct ways in which you can climb to the top.

```JSAV
var arr = jsav.ds.array([1, 2], {indexed: true});
jsav.label("You can only climb 1 or 2 steps at a time");
```
Note: This was included because the student had trouble understanding the constraints of the problem, specifically that they can only climb 1 or 2 steps at a time.
[/NOTE]

## Solution

### Optimized Approach using Dynamic Programming

[NOTE]
We can solve this problem using dynamic programming. The key idea is to realize that the number of ways to reach the i-th step depends only on the number of ways to reach the (i-1)-th step and the (i-2)-th step. Let's define `dp[i]` as the number of distinct ways to climb to the i-th step. Then, we have the following recurrence relation:

```
dp[i] = dp[i-1] + dp[i-2]
```

This is because to reach the i-th step, we can either climb 1 step from the (i-1)-th step or climb 2 steps from the (i-2)-th step.

```JSAV
var arr = jsav.ds.array([0, 0, 0, 0, 0, 0], {indexed: true});
arr.css({marginTop : 50});
jsav.label("DP Array");
jsav.pointer("i", arr.index(2));
jsav.label("To reach step i, we can either climb 1 step from step i-1 or 2 steps from step i-2");
```
Note: This was included because the student had trouble understanding how to apply dynamic programming to this problem, specifically how to use the number of ways to climb 'i-1' and 'i-2' steps to calculate the number of ways to climb 'i' steps.
[/NOTE]

#### Step-by-step Solution Construction

1. [NOTE]
Create an array `dp` of size `n+1` to store the number of ways to climb to each step. We use `n+1` to handle the base case where there are 0 steps.

```JSAV
var arr = jsav.ds.array([0, 0, 0, 0, 0, 0], {indexed: true});
jsav.label("DP Array of size n+1");
```
Note: This was included because the student had trouble understanding why they need to create a list of size n+1 if there are n steps.
[/NOTE]

2. [NOTE]
Initialize the base cases:
   - `dp[0] = 1`: There is only one way to climb 0 steps, which is to not climb at all.
   - `dp[1] = 1`: There is only one way to climb 1 step.

```JSAV
var arr = jsav.ds.array([1, 1, 0, 0, 0, 0], {indexed: true});
arr.highlight(0);
arr.highlight(1);
jsav.label("Initialize base cases: dp[0] = 1, dp[1] = 1");
```
Note: This was included because the student correctly identified the base cases for the problem, showing that they understand the initial conditions for the dynamic programming solution.
[/NOTE]

3. [NOTE]
Iterate from `i = 2` to `n` and fill the `dp` array using the recurrence relation:

```
dp[i] = dp[i-1] + dp[i-2]
```

```JSAV
var arr = jsav.ds.array([1, 1, 0, 0, 0, 0], {indexed: true});
arr.css({marginTop : 50});
jsav.pointer("i", arr.index(2));
jsav.label("Fill dp array using recurrence relation");
```

```JSAV
var arr = jsav.ds.array([1, 1, 2, 0, 0, 0], {indexed: true});
arr.css({marginTop : 50});
arr.highlight(2);
jsav.pointer("i", arr.index(3));
```

```JSAV
var arr = jsav.ds.array([1, 1, 2, 3, 0, 0], {indexed: true});
arr.css({marginTop : 50});
arr.highlight(3);
jsav.pointer("i", arr.index(4));
```

```JSAV
var arr = jsav.ds.array([1, 1, 2, 3, 5, 0], {indexed: true});
arr.css({marginTop : 50});
arr.highlight(4);
jsav.pointer("i", arr.index(5));
```
Note: This was included because the student had trouble understanding how to use the number of ways to climb 'i-1' and 'i-2' steps to calculate the number of ways to climb 'i' steps.
[/NOTE]

4. [NOTE]
Return `dp[n]`, which represents the number of distinct ways to climb to the top (the n-th step).

```JSAV
var arr = jsav.ds.array([1, 1, 2, 3, 5, 8], {indexed: true});
arr.highlight(5);
jsav.label("Return dp[n] = 8");
```
Note: This was included because the student was returning the entire dp array instead of the number of distinct ways to climb to the top.
[/NOTE]

#### Code

```python
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]
```

#### Solution Summary

- We create an array `dp` of size `n+1` to store the number of ways to climb to each step.
- We initialize the base cases `dp[0] = 1` and `dp[1] = 1`.
- We iterate from `i = 2` to `n` and fill the `dp` array using the recurrence relation `dp[i] = dp[i-1] + dp[i-2]`.
- Finally, we return `dp[n]`, which represents the number of distinct ways to climb to the top.

```JSAV
var arr = jsav.ds.array([1, 1, 2, 3, 5, 8], {indexed: true});
jsav.label("DP Array filled using recurrence relation");
```

#### Time Complexity

The time complexity of this solution is O(n) because we iterate from 2 to n to fill the `dp` array.

#### Space Complexity

The space complexity is O(n) as we use an array of size `n+1` to store the intermediate results.

## Addressing Knowledge Gaps

Based on the tutoring session transcript, here are some points to emphasize:

1. **Understanding the Problem**: Make sure you understand the key components of the problem, such as the constraints (you can only climb 1 or 2 steps at a time) and the desired output (the number of distinct ways to climb to the top). Don't get confused by considering climbing more than 2 steps at a time.

```JSAV
var arr = jsav.ds.array([1, 2], {indexed: true});
jsav.label("You can only climb 1 or 2 steps at a time");
```

2. **Applying Dynamic Programming**: Recognize that this problem can be solved using dynamic programming. The number of ways to reach the i-th step depends only on the number of ways to reach the (i-1)-th step and the (i-2)-th step. Use this recurrence relation to fill the `dp` array.

```JSAV
var arr = jsav.ds.array([0, 0, 0, 0, 0, 0], {indexed: true});
arr.css({marginTop : 50});
jsav.pointer("i", arr.index(2));
jsav.label("Number of ways to reach step i depends on steps i-1 and i-2");
```

3. **Handling Base Cases**: To handle the base case where there are 0 steps, create a `dp` array of size `n+1`. Initialize `dp[0] = 1` and `dp[1] = 1` as the base cases.

```JSAV
var arr = jsav.ds.array([1, 1, 0, 0, 0, 0], {indexed: true});
arr.highlight(0);
arr.highlight(1);
jsav.label("Initialize base cases: dp[0] = 1, dp[1] = 1");
```

4. **Python List Operations**: Be careful when creating and manipulating lists in Python. To create a list of size `n+1` initialized with zeros, use `dp = [0] * (n + 1)`. Avoid syntax errors and incorrect list operations.

```JSAV
var arr = jsav.ds.array([0, 0, 0, 0, 0, 0], {indexed: true});
jsav.label("Create DP array of size n+1 initialized with zeros");
```

5. **Returning the Result**: Remember to return `dp[n]`, which represents the number of distinct ways to climb to the top (the n-th step). Don't return the entire `dp` array.

```JSAV
var arr = jsav.ds.array([1, 1, 2, 3, 5, 8], {indexed: true});
arr.highlight(5);
jsav.label("Return dp[n] = 8");
```

By understanding these key points and addressing the knowledge gaps, you'll be able to solve the Climbing Stairs problem effectively using dynamic programming.

## Recommended Problems
1. [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) - This problem is similar to Climbing Stairs but with an added cost factor. It will help reinforce the concept of dynamic programming and recurrence relations.

2. [House Robber](https://leetcode.com/problems/house-robber/) - This problem also uses dynamic programming and has a similar recurrence relation to Climbing Stairs. It will help strengthen your understanding of how to apply dynamic programming to solve optimization problems.

3. [Fibonacci Number](https://leetcode.com/problems/fibonacci-number/) - The Fibonacci sequence is a classic example of dynamic programming. Solving this problem will help you understand the basics of dynamic programming and how to optimize recursive solutions using memoization or tabulation.

4. [N-th Tribonacci Number](https://leetcode.com/problems/n-th-tribonacci-number/) - This problem is an extension of the Fibonacci sequence and will help you practice applying dynamic programming to similar problems with slightly different recurrence relations.

5. [Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/) - While not directly related to Climbing Stairs, this problem will help you practice creating and manipulating 2D arrays in Python. It also involves a recurrence relation similar to the one used in Climbing Stairs.