Java Solution for Counting Ways to Climb Stairs | StudyEcart | Hacker Rank Solutions

Problem Statement

You are given `n` stairs and a person at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Your task is to count the number of ways the person can reach the top, considering the climbing order.

 Example 1

Input: n=4

Output: 5

Explanation:

To reach the 4th stair, there are 5 different ways:

1. Climb 1 stair, then 1 stair, then 1 stair, then 1 stair.

2. Climb 2 stairs, then 1 stair, then 1 stair.

3. Climb 1 stair, then 2 stairs, then 1 stair.

4. Climb 1 stair, then 1 stair, then 2 stairs.

5. Climb 2 stairs, then 2 stairs.

Example 2 :

Input: n=10
Output: 89

Explanation:

There are 89 ways to reach the 10th stair.

Solution: Dynamic Programming Approach

 Steps:

1. Understand the Problem: We want to find the number of ways a person can reach the `n`-th stair by climbing 1 or 2 stairs at a time.

2. Recursive Pattern: The number of ways to reach the `i`-th stair is the sum of the number of ways to reach the `(i-1)`-th stair and the `(i-2)`-th stair.

3. Dynamic Programming Table:  Create an array `dp[]`, where `dp[i]` represents the number of ways to reach the `i`-th stair.

4. Fill the DP Table:  Initialize `dp[0]` as 1 and `dp[1]` as 1 (base cases). For each stair `i` from 2 to `n`, set `dp[i]` as the sum of `dp[i-1]` and `dp[i-2]`.

5. Return the Result:  The answer we're looking for is `dp[n]`, which represents the number of ways to reach the `n`-th stair.

 Java Code:

 
  import java.util.Scanner;

public class StairClimbingWays {
    public static int countWaysToReachTop(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the number of stairs: ");
        int n = scanner.nextInt();

        int ways = countWaysToReachTop(n);
        System.out.println("Ways to reach " + n + " stairs: " + ways);

        scanner.close();
    }
}

  

(code-box) 

This Java code demonstrates the dynamic programming solution for counting the ways to climb stairs. It's essential to break down each solution step to help your readers understand the problem-solving approach.

Boost your Java programming skills with these top 10 beginner-friendly Java programs! Check them out Clickhere.

🚀 Elevate Your Career with Studyecart! 📚📊

🔥 Get instant job notifications and ace interviews with Studyecart. 📌

Download

#StudyecartApp #CareerBoost