Climbing Stairs: A Dynamic Programming Approach

The "Climbing Stairs" problem is a classic example used to illustrate dynamic programming in algorithmic problem-solving. It involves finding the number of distinct ways to climb a staircase with a given number of steps.

Problem Statement

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

Examples

• Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top:

  1. 1 step + 1 step
  2. 2 steps

• 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

Dynamic Programming Solution

Here's how you can solve this problem using dynamic programming in JavaScript:

Breaking Down the Solution

• Base Cases: If n is 1, the answer is straightforwardly 1. The dynamic programming array dp is initialized with its base cases: dp[0] = 1 and dp[1] = 2. These represent the number of ways to climb a staircase with one step and two steps, respectively.

• Filling the dp Array: For each step from 2 to n - 1, the function calculates the number of ways to reach that step. The value of dp[i] is determined as the sum of dp[i - 1] and dp[i - 2]. This represents the total ways to climb to the current step, either by taking one step from the previous step or two steps from the step before that.

• Returning the Result: The final result is stored in dp[n - 1], which gives the total number of distinct ways to reach the top of the staircase. This value is returned as the solution to the problem.

Conclusion

The "Climbing Stairs" problem is a classic example that showcases the efficacy of dynamic programming in solving computational problems related to combinations and counting. It emphasizes the importance of breaking down the problem into smaller, overlapping subproblems and building up the solution by storing and reusing intermediate results. This approach not only makes the solution more efficient but also simplifies the process of solving complex problems.

Rust Solution

Rust's vec![1, 2] macro seeds the DP array, and since you can't index-assign past a vector's current length the loop grows it with dp.push(...) instead of JS's dp[i] = .... Vector indices are usize, so both the range bound 2..n as usize and the final lookup dp[(n-1) as usize] cast the i32 argument explicitly. The binding is spelled let mut dp because the pushes mutate it, and the trailing dp[(n-1) as usize] is returned as a tail expression with no semicolon — unlike the explicit return 1 guard above it.

Go Solution

Go grows the slice with dp = append(dp, dp[i-1]+dp[i-2]) — append may reallocate and hands back a possibly-new slice header, so its result must be reassigned to dp rather than discarded. The array is a []int slice built with the := short declaration and the composite literal []int{1, 2}, and because Go indexes slices with plain int, dp[i-1] and dp[n-1] index directly with no usize-style cast. The loop is the classic three-clause for i := 2; i < n; i++ rather than a range expression.