Return the number of unique ways you can climb the staircase 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 &lt; X.length &amp;&amp; (N - X[i] &gt;= 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?
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] &gt;= 0 use N &gt;= 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 &lt;= totalStairs; numStairs++) {
        for (int stepSize : stepSizeOptions) {
            if (numStairs &gt;= stepSize) {
                numberWays[numStairs] += numberWays[numStairs - stepSize];
            }
        }
    }

    return numberWays[totalStairs];
}