1
\$\begingroup\$

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?

\$\endgroup\$
  • 2
    \$\begingroup\$ You know, most of the things in the replies you've received in your previous questions apply to this too. You should start by applying them to your coding style instead of making us waste our time repeating the same things over and over again. Please don't treat this site as a place where you just dump your coding challenge answers to get a better score. You're diminishing the value of this site for the people who want to learn to be better programmers. \$\endgroup\$ – TorbenPutkonen Mar 22 '19 at 6:00
1
\$\begingroup\$

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];
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.