Climbing Stairs

                                            
class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
};

                                            
class Solution {
    public 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];
    }
}

                                            
class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return 1
        first, second = 1, 2
        for i in range(3, n+1):
            third = first + second
            first = second
            second = third
        return second

                                            
int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    
    int first = 1;
    int second = 2;
    
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
    
    return second;
}

                                            
public class Solution {
    public 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];
    }
}

                                            
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if (n === 1) return 1;
    let dp = new Array(n + 1).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

                                            
function climbStairs(n: number): number {
    if (n === 1) {
        return 1;
    }
    
    let first = 1;
    let second = 2;
    
    for (let i = 3; i <= n; i++) {
        let third = first + second;
        first = second;
        second = third;
    }
    
    return second;
};

                                            
class Solution {
    /**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
        if ($n == 1) {
            return 1;
        }
        $dp = array_fill(0, $n+1, 0);
        $dp[1] = 1;
        $dp[2] = 2;
        for ($i = 3; $i <= $n; $i++) {
            $dp[$i] = $dp[$i-1] + $dp[$i-2];
        }
        return $dp[$n];
    }
}

                                            
class Solution {
    fun climbStairs(n: Int): Int {
        if (n == 1) return 1
        if (n == 2) return 2
        
        var first = 1
        var second = 2
        var third = 0
        
        for (i in 3..n) {
            third = first + second
            first = second
            second = third
        }
        
        return third
    }
}

                                            
class Solution {
  int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    int first = 1;
    int second = 2;
    for (int i = 3; i <= n; i++) {
      int third = first + second;
      first = second;
      second = third;
    }
    
    return second;
  }
}

                                            
func climbStairs(n int) int {
    if n == 1 {
        return 1
    }
    
    first, second := 1, 2
    for i := 3; i <= n; i++ {
        third := first + second
        first = second
        second = third
    }
    
    return second
}

                                            
# @param {Integer} n
# @return {Integer}
def climb_stairs(n)
    return 1 if n == 1
    first = 1
    second = 2
    for i in 3..n
        third = first + second
        first = second
        second = third
    end
    return second
end

                                            
object Solution {
    def climbStairs(n: Int): Int = {
        if (n == 1) return 1
        if (n == 2) return 2

        var dp = Array.ofDim[Int](n + 1)
        dp(1) = 1
        dp(2) = 2

        for (i <- 3 to n) {
            dp(i) = dp(i - 1) + dp(i - 2)
        }

        dp(n)
    }
}

                                            
impl Solution {
    pub fn climb_stairs(n: i32) -> i32 {
        if n <= 2 {
            return n;
        }

        let mut dp = vec![0; n as usize + 1];
        dp[1] = 1;
        dp[2] = 2;
        
        for i in 3..=n {
            dp[i as usize] = dp[i as usize - 1] + dp[i as usize - 2];
        }
        
        dp[n as usize]
    }
}

                                            
(define/contract (climb-stairs n)
  (-> exact-integer? exact-integer?)
  (cond
    [(= n 1) 1]
    [(= n 2) 2]
    [else (+ (climb-stairs (- n 1)) (climb-stairs (- n 2)))]
  )
)

To solve this coding challenge, we need to determine the number of distinct ways to climb to the top of a staircase with

n

steps, where at each step you can either take 1 or 2 steps. The problem can intuitively be understood as a form of the Fibonacci sequence, where the number of ways to reach the nth step is the sum of the ways to reach the (n-1)th and (n-2)th steps.

Explanation

The problem can be broken down into smaller subproblems, and a dynamic programming approach can be used to solve it efficiently. Here are the steps to solve the problem:

Base Cases :

If there is only 1 step (
n = 1

), there is only one way to climb it: take 1 step.
If there are 2 steps (
n = 2

), there are two ways to climb it: take two 1 steps, or take one 2-step.

State Transition :

For
n >= 3

, to reach the nth step, we can either:

Come from the (n-1)th step by taking 1 step or
Come from the (n-2)th step by taking 2 steps.

Therefore, the number of ways to reach the nth step can be formulated as:

f(n) = f(n-1) + f(n-2)

This is similar to the Fibonacci sequence where each number is the sum of the two preceding ones.

Iteration :

We can use iteration to compute the values from the base cases up to the required nth step.

Below is the pseudocode with comments for the complete solution:

                                            
function climbStairs(steps):
# If there is only 1 step, there's only one way to climb it
if steps == 1:
return 1

# Initialize variables to store the number of ways to reach the first and second step
num_ways_one_step_before = 1  # Ways to reach step 1
num_ways_two_steps_before = 2  # Ways to reach step 2

# Loop starts at step 3 and goes up to the required number of steps
for current_step in range(3, steps + 1):
# Calculate number of ways to reach the current step
num_ways_current_step = num_ways_one_step_before + num_ways_two_steps_before

# Update the variables for the next iteration
num_ways_one_step_before = num_ways_two_steps_before
num_ways_two_steps_before = num_ways_current_step

# Return the number of ways to reach the nth step
return num_ways_two_steps_before

Step-by-Step Explanation

Initial Check :

If
steps

is 1, directly return 1 as there's only one way to reach step 1.

Variable Initialization :

Initialize two variables to track the number of ways to reach the preceding two steps.
num_ways_one_step_before

is initialized to 1 for the first step, and
num_ways_two_steps_before

is initialized to 2 for the second step.

Loop Through Steps :

Use a loop starting from step 3 up to the desired number of steps. In each iteration:

Compute the number of ways to reach the current step by summing the ways to reach the two previous steps.
Update the tracking variables to reflect the ways to reach the last two steps for use in the next iteration.

Return Result :

After the loop ends, the variable
num_ways_two_steps_before

will contain the number of ways to reach the nth step. Return this value.

By following these detailed steps and using the provided pseudocode, you can determine the number of ways to climb a staircase with

n

steps by either taking 1 step or 2 steps at a time.