Problem Explanation

You are climbing a staircase that has n steps. The task is to calculate how many distinct ways there are for you to climb to the top. The catch is that you can only climb 1 or 2 steps at a time.

The steps will always be positive and unique.

Let's walk through an example to understand the problem better:

Example:

1
2
3n = 3

The possible ways to climb to the top are:

1. Climb 1 step, then 2 steps
2. Climb 2 steps, then 1 step
3. Climb 1 step three times

Output: 3

Approach

The key to solving this problem is understanding that it's a dynamic programming problem. Dynamic programming is a method for solving problems by breaking it down into smaller subproblems, solving each of those subproblems just once, and storing their solutions in case next time the same subproblem occurs.

The steps to reach the i-th stair will be the sum of the steps to reach the (i-1)-th and (i-2)-th stairs because those are the only 2 ways to reach the i-th stair (either from (i-1)-th stair or from (i-2)-th stair).

Solutions

Python Solution

1
2python
3class Solution:
4  def climbStairs(self, n: int) -> int:
5    # Initialize dp array with 1's
6    dp = [1 for _ in range(n+1)]
7    
8    # Loop from 2 to n
9    for i in range(2, n+1):
10      # dp[i] is the sum of dp[i-1] and dp[i-2]
11      dp[i] = dp[i-1] + dp[i-2]
12      
13    # Return dp[n]
14    return dp[n]

Java Solution

1
2java
3class Solution {
4  public int climbStairs(int n) {
5    // Create dp array
6    int[] dp = new int[n+1];
7    // Initialize base cases
8    dp[0] = 1;
9    dp[1] = 1;
10
11    // Loop from 2 to n
12    for(int i=2; i<=n; i++){
13      // dp[i] is the sum of dp[i-1] and dp[i-2]
14      dp[i] = dp[i-1] + dp[i-2];
15    }
16    
17    // Return dp[n]
18    return dp[n];
19  }
20}

JavaScript Solution

1
2javascript
3var climbStairs = function(n) {
4  let dp = new Array(n + 1);
5  dp[0] = 1;
6  dp[1] = 1;
7
8  for(let i = 2; i <= n; i++){
9    dp[i] = dp[i - 1] + dp[i - 2];
10  }
11
12  return dp[n];
13};

C++ Solution

1
2c++
3class Solution {
4public:
5  int climbStairs(int n) {
6    vector<int> dp(n + 1);
7    dp[0] = 1;
8    dp[1] = 1;
9
10    for(int i = 2; i <= n; i++)
11      dp[i] = dp[i - 1] + dp[i - 2];
12      
13    return dp[n];
14  }
15};

C# Solution

1
2csharp
3public class Solution {
4  public int ClimbStairs(int n) {
5    int[] dp = new int[n+1];
6    dp[0] = 1;
7    dp[1] = 1;
8
9    for(int i=2; i<=n; i++){
10      dp[i] = dp[i-1] + dp[i-2];
11    }
12
13    return dp[n];
14  }
15}

That's it! We've now solved the problem and calculated the number of distinct ways to climb a staircase in each of the programming languages.In all of these solutions, we're using dynamic programming to reduce the problem into subproblems, and then storing the results of these subproblems so we can use them multiple times, reducing repeated calculations.

We start all solutions by initializing an array (dp) to store the number of ways to reach the stairs. For stairs 0 and 1, there is clearly a single way to get there. Hence, dp[0] and dp[1] are both initialized to 1.

Afterwards, we use a loop that starts from 2 and goes up to n, calculating the number of ways to reach i-th stair, which is the sum of ways of reaching (i-1)-th and (i-2)-th stairs.

Finally, we return dp[n], which is the number of ways to reach the top of the staircase. This is our final solution.

Note that this approach has a time complexity of O(n), which is the time taken to fill up the dp array. In terms of space complexity, it is also O(n) due to the space used to create the dp array.

This problem is a classical dynamic programming problem and understanding how to solve it will help you tackle many other similar problems that require breaking down a problem into smaller sub-problems and storing the results for re-use.