Java - Ways to Reach the nth Stair

Problem Statement

You can climb either 1 step or 2 steps at a time. Given a number n, find the number of distinct ways to reach the nth stair.

Example

Input: n = 4

Output: 5

Explanation:

1+1+1+1

1+2+1

2+1+1

1+1+2

2+2

Java Code – Dynamic Programming

public class StairClimberDP {

    public static int countWays(int n) {

        if (n == 0 || n == 1)

            return 1;

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

        dp[0] = 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) {

        int n = 4;

        System.out.println("Number of ways to reach the " + n + "th stair: " + countWays(n));

    }

}

Optimized Version (O(1) Space)

public class StairClimberOptimized {

    public static int countWays(int n) {

        if (n == 0 || n == 1)

            return 1;

        int a = 1, b = 1;

        int current = 0;

        for (int i = 2; i <= n; i++) {

            current = a + b;

            a = b;

            b = current;

        }

        return current;

    }

    public static void main(String[] args) {

        int n = 4;

        System.out.println("Number of ways to reach the " + n + "th stair: " + countWays(n));

    }

}