java - Count number of possible paths up ladder

Question

I can't seem to come up with an algorithm to solve the following problem, I tried using a series of for-loops but it became way too complicated:

A ladder has n steps, one can climb the ladder using any combination of steps of 1 or steps of 2. How many possible ways are there for one to climb the ladder?

So for example, if the ladder had 3 steps, these would be the possible paths:

• 1-1-1
• 2-1
• 1-2

And for 4 steps

• 1-1-1-1
• 2-1-1
• 1-2-1
• 1-1-2
• 2-2

Any insight as to how this could be done would be greatly appreciated. Also, I'm working in Java.

Edit: I was indeed going to be using small n values, but it certainly would be neat to know how to manage with larger ones.

Answer 1

Interestingly, there is a simple solution to this problem. You can use recursion:

public static int countPossibilities(int n) {
    if (n == 1 || n == 2) return n;
    return countPossibilities(n - 1) + countPossibilities(n - 2);
}

Whenever you're faced with this type of "tricky" problem, bear in mind that the solution is often times quite elegant, and always check to see if something can be done with recursion.

EDIT: I was assuming that you would deal with relatively small n values in this problem, but if you deal with large ones then the method above will probably take a good amount of time to finish. One solution would be to use a Map that would map n to countPossibilities(n) - this way, there would be no time wasted doing a computation that you've already done. Something like this:

private static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
static {
    map.put(1, 1);
    map.put(2, 2);
}

public static int countPossibilities(int n) {
    if (map.containsKey(n))
        return map.get(n);

    int a, b;

    if (map.containsKey(n - 1))
        a = map.get(n - 1);
    else {
        a = countPossibilities(n - 1);
        map.put(n - 1, a);
    }

    if (map.containsKey(n - 2))
        b = map.get(n - 2);
    else {
        b = countPossibilities(n - 2);
        map.put(n - 2, b);
    }

    return a + b;
}

Try this with n = 1000. The second method is literally orders of magnitude faster than the first one.