Climbing Stairs In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 step or 2 steps. In how many distinct ways can you reach the top?

Example 1:

Input:

n = 2

Output:

2

Explanation: There are two ways to reach the top:

1. 1 step + 1 step
2. 2 steps

Example 2:

Input:

n = 3

Output:

3

Explanation: There are three ways to reach the top:

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

---

Approach:

The problem is a variation of the Fibonacci sequence, where each step can be reached from either the previous step (taking 1 step) or the step before that (taking 2 steps).

Let’s define dp[i] as the number of distinct ways to reach the i-th step.

Recurrence Relation:

To reach step i, you can either:

• Come from step i-1 by taking 1 step, or
• Come from step i-2 by taking 2 steps.

Thus, the recurrence relation is:dp[i]=dp[i−1]+dp[i−2]dp[i] = dp[i-1] + dp[i-2]dp[i]=dp[i−1]+dp[i−2]

Base Cases:

• dp[0] = 1 (there is 1 way to stay on the ground, doing nothing)
• dp[1] = 1 (there is only 1 way to reach the first step, taking 1 step)

Final Answer:

The answer will be dp[n], where n is the number of steps.

Time and Space Complexity:

• Time Complexity: O(n), where n is the number of steps. We iterate once to fill the DP table.
• Space Complexity: O(n), for the DP table. We can optimize it to O(1) by using two variables, as we only need the last two values.

---

Code Implementations in Different Languages:

1. C Language (DP Approach):

#include <stdio.h>

int climbStairs(int n) {
    if (n == 1) return 1;
    int prev2 = 1, prev1 = 1;
    int current;
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

int main() {
    int n = 3;
    printf("Ways to climb %d stairs: %d\n", n, climbStairs(n));  // Output: 3
    return 0;
}

2. C++ Language (DP Approach):

#include <iostream>
using namespace std;

int climbStairs(int n) {
    if (n == 1) return 1;
    int prev2 = 1, prev1 = 1, current;
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

int main() {
    int n = 3;
    cout << "Ways to climb " << n << " stairs: " << climbStairs(n) << endl;  // Output: 3
    return 0;
}

3. Java (DP Approach):

public class ClimbingStairs {
    public static int climbStairs(int n) {
        if (n == 1) return 1;
        int prev2 = 1, prev1 = 1, current;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    public static void main(String[] args) {
        int n = 3;
        System.out.println("Ways to climb " + n + " stairs: " + climbStairs(n));  // Output: 3
    }
}

4. Python (DP Approach):

def climbStairs(n):
    if n == 1:
        return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    return prev1

# Test case
n = 3
print(f"Ways to climb {n} stairs: {climbStairs(n)}")  # Output: 3

5. C# (DP Approach):

using System;

class Program {
    public static int ClimbStairs(int n) {
        if (n == 1) return 1;
        int prev2 = 1, prev1 = 1, current;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }

    static void Main() {
        int n = 3;
        Console.WriteLine($"Ways to climb {n} stairs: {ClimbStairs(n)}");  // Output: 3
    }
}

6. JavaScript (DP Approach):

function climbStairs(n) {
    if (n === 1) return 1;
    let prev2 = 1, prev1 = 1, current;
    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

// Test case
const n = 3;
console.log(`Ways to climb ${n} stairs: ${climbStairs(n)}`);  // Output: 3

---

Complexity Analysis:

Time Complexity:

• Time Complexity: O(n), where n is the number of steps. We only iterate once through the range from 2 to n.

Space Complexity:

• Space Complexity: O(1). We only need two variables (prev1 and prev2) to store the results of the previous two steps, optimizing the space usage.

Conclusion:

The Climbing Stairs problem can be efficiently solved using dynamic programming. By iterating over the steps and using the recurrence relation, we can calculate the number of ways to reach the top in linear time, with constant space complexity.