java - 计算梯子上可能的路径数

Question

我似乎无法想出解决以下问题的算法，我尝试使用一系列 for 循环，但它变得太复杂了:

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?

例如，如果梯子有3 个台阶，则可能的路径如下:

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

4 步

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

任何关于如何做到这一点的见解都将不胜感激。另外，我在 Java 工作。

编辑:我确实打算使用较小的 n 值，但知道如何处理较大的值肯定会很好。

Answer 1

有趣的是，这个问题有一个简单的解决方案。您可以使用递归:

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

每当您遇到此类“棘手”问题时，请记住解决方案通常非常优雅，并始终检查是否可以通过递归完成某些事情。

编辑:我假设您会在这个问题中处理相对较小的 n 值，但如果您处理较大的值，那么上述方法可能需要完成的时间很长。一种解决方案是使用 Map 将 n 映射到 countPossibilities(n) - 这样，就不会浪费时间做你已经完成的计算。像这样:

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;
}

尝试使用 n = 1000。第二种方法实际上比第一种方法快几个数量级。