Problem Statement (Asked By Amazon)

There is a staircase with N steps, and you can ascend either 1 step or 2 steps at a time. Write a function to calculate the number of unique ways to climb the staircase. The sequence of steps matters.

Example:

If N = 4, there are 5 unique ways to climb the staircase:

• 1, 1, 1, 1
• 2, 1, 1
• 1, 2, 1
• 1, 1, 2
• 2, 2

Follow-up:
What if, instead of climbing 1 or 2 steps at a time, you could climb any number of steps from a given set of positive integers X? For instance, if X = {1, 3, 5}, you could ascend 1, 3, or 5 steps at a time.

Problem link: https://leetcode.com/problems/climbing-stairs/description/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

We’ll start with some test cases to identify a pattern:

• N = 1: [1] → 1 way
• N = 2: [1,1]→ 2 ways
• N = 3: [1,2],[1,1,1],[2,1] → 3 ways
• N = 4: [1,1,2],[2,2],[1,2,1],[1,1,1,1],[2,1,1] → 5 ways

Notice the relationship:
To get to step N, we can either:

• Take a single step from N−1, or
• Take two steps from N−2.

Thus, f(N)=f(N−1)+f(N−2), which is the Fibonacci sequence.

Recursive Solution (Inefficient, O(2^N)):

public class Staircase {
    public static int staircase(int n) {
        if (n <= 1) {
            return 1;
        }
        return staircase(n - 1) + staircase(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(staircase(4)); // Output: 5
    }
}

This solution is simple but inefficient due to repeated calculations.

Iterative Solution (Efficient, O(N)):

We can optimize by iteratively calculating the result, storing only the last two values.

public class Staircase {
    public static int staircase(int n) {
        if (n <= 1) {
            return 1;
        }
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }

    public static void main(String[] args) {
        System.out.println(staircase(4)); // Output: 5
    }
}

This runs in O(N) time and uses O(1) space.

Generalized Solution (Steps from Set X):

Now let’s generalize to allow any set of steps X. For example, if X={1,3,5} then:f(n)=f(n−1)+f(n−3)+f(n−5)

Recursive Generalized Solution (Inefficient):

import java.util.Set;

public class Staircase {
    public static int staircase(int n, Set<Integer> X) {
        if (n < 0) {
            return 0;
        }
        if (n == 0) {
            return 1;
        }
        int total = 0;
        for (int step : X) {
            total += staircase(n - step, X);
        }
        return total;
    }

    public static void main(String[] args) {
        System.out.println(staircase(4, Set.of(1, 2))); // Output: 5
        System.out.println(staircase(4, Set.of(1, 3, 5))); // Output: 3
    }
}

This approach is slow due to repeated computations.

Optimized Generalized Solution (Dynamic Programming, O(N×∣X∣)):

We use a cache to store intermediate results and build the solution iteratively.

import java.util.Set;

public class Staircase {
    public static int staircase(int n, Set<Integer> X) {
        int[] cache = new int[n + 1];
        cache[0] = 1; // Base case: 1 way to get to step 0

        for (int i = 1; i <= n; i++) {
            for (int step : X) {
                if (i - step >= 0) {
                    cache[i] += cache[i - step];
                }
            }
        }
        return cache[n];
    }

    public static void main(String[] args) {
        System.out.println(staircase(4, Set.of(1, 2))); // Output: 5
        System.out.println(staircase(4, Set.of(1, 3, 5))); // Output: 3
    }
}

Explanation:

1. Base Case:
   • cache[0]=1, since there’s one way to stay at step 0 (doing nothing).
2. Iterative Calculation:
   • For each step iii, sum the number of ways to reach i−x for all x∈X (valid steps).
3. Final Result:
   • The number of ways to reach step n is stored in cache[n].

Complexity:

• Time Complexity: O(N×∣X∣) — For each of the N steps, we iterate over the set X.
• Space Complexity: O(N) — The size of the cache.

This approach is both time and space-efficient for solving the generalized staircase problem.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.