Return the number of unique ways you can climb the staircase

Question

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = {1, 3, 5}, you could climb 1, 3, or 5 steps at a time.

public class DailyCodingProblem12 {
    public static void main(String args[]) {
        int[] X = { 1, 2 };
        int N = 4;
        int result = solution(N, X);
        System.out.println(result);

        int[] X1 = { 1, 2, 3 };
        N = 4;
        result = solution(N, X1);
        System.out.println(result);

        int[] X2 = { 1, 2, 3 };
        N = 3;
        result = solution(N, X2);
        System.out.println(result);
    }

    static int solution(int N, int[] X) {
        int[] memory = new int[N + 1];
        memory[0] = 1;
        memory[1] = 1;
        return noOfWays(N, X, memory);
    }

    static int noOfWays(int N, int[] X, int[] memory) {
        if (memory[N] != 0) {
            return memory[N];
        }
        int noOfWays = 0;
        for (int i = 0; i < X.length && (N - X[i] >= 0); i++) {
            memory[N - X[i]] = noOfWays(N - X[i], X, memory);
            noOfWays += memory[N - X[i]];
        }
        return noOfWays;

    }

}

How do I improve my solution? There is a way to save more space?

Answer 1

Dynamic programming approach

My main advice is to prefer bottom-up iteration to top-down memoization. These are the two main approaches to dynamic programming as described on Wikipedia. Now, while there is nothing absolutely wrong with top-down approaches, bottom-up is, at least for this problem

• cleaner to code
• does not take up space on the stack
• runs faster if method calls are slower than iteration

Finally, your code may re-compute the same values multiple times. This is not true of all top-down approaches, but is easy to avoid using bottom-up dynamic programming.

Bugs

• incorrect if X is not sorted
• incorrect if X does not contain 1 due to unnecessary memory[1] = 1

Minor style points

• use more descriptive class and variable names
• instead of N - X[i] >= 0 use N >= X[i]
• prefer enhanced for loops

static int solution(int totalStairs, int[] stepSizeOptions) {
    int[] numberWays = new int[totalStairs+1];
    numberWays[0] = 1;

    for (int numStairs = 1; numStairs <= totalStairs; numStairs++) {
        for (int stepSize : stepSizeOptions) {
            if (numStairs >= stepSize) {
                numberWays[numStairs] += numberWays[numStairs - stepSize];
            }
        }
    }

    return numberWays[totalStairs];
}