Climbing Stairs - Java Solution

1. Introduction

This blog post delves into a classic problem often encountered in dynamic programming and combinatorics - the "Climbing Stairs" problem. It's a problem that models a situation where one needs to determine the number of distinct ways to reach the top of a staircase, given that each step can either be 1 or 2 steps at a time.

Problem

Given a staircase with n steps, the task is to find out how many distinct ways there are to climb to the top. At each step, you can choose to climb either 1 step or 2 steps.

2. Solution Steps

1. Recognize that this is a Fibonacci sequence problem, where the number of ways to reach the nth step is the sum of ways to reach the (n-1)th step and the (n-2)th step.

2. Use dynamic programming to build up the solution from the base cases.

3. Initialize an array dp with a size of n + 1.

4. Set the base cases: dp[1] = 1 and dp[2] = 2.

5. Iterate from 3 to n, calculating dp[i] as dp[i-1] + dp[i-2].

6. Return dp[n], which represents the number of ways to reach the top.

3. Code Program

public class ClimbingStairs {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(climbStairs(n)); // Test the function
    }

    // Function to calculate the number of ways to climb stairs
    public static 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];
    }
}

Output:

8

Explanation:

1. climbStairs: This function calculates the number of ways to climb to the top of a staircase with n steps.

2. It handles the base case where n is 1. In this case, there's only one way to climb.

3. The function initializes a dynamic programming array dp, where dp[i] represents the number of ways to reach step i.

4. It sets the base cases for dp[1] and dp[2].

5. The function then iteratively computes the values of dp[i] for i from 3 to n using the relation dp[i] = dp[i - 1] + dp[i - 2]. This relation follows from the fact that to reach the ith step, one can come either from the (i-1)th step or the (i-2)th step.

6. The final result dp[n] is the total number of distinct ways to reach the top of the stairs.

7. This approach efficiently computes the result using dynamic programming to avoid redundant calculations.