计算梯子上可能路径的数量

Question

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

梯子有n台阶,人们可以使用1步或2步的任意组合爬上梯子.有多少种方法可以让人爬上梯子？

因此,例如,如果梯子有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.第二种方法比第一种方法快几个数量级.

Answer 2

这实际上与Fibonacci序列密切相关,正如目前为止的评论中仅简要提到的那样:每个步骤n都可以从下面的两个步骤(n-2)或下面的一个步骤(n-1)中达到,因此达到的可能性的数量该步骤是达到其他两个步骤的可能性的总和.最后,只有一种可能性到达第一步(和第二步,即停留在地面上).

此外,作为对步可能性的数量n仅依赖于结果的步骤n-1和n-2,没有必要对所有这些中间值存储在地图或阵列-最后两个够了!

public static long possForStep(int n) {
    // current and last value, initially for n = 0 and n = 1
    long cur = 1, last = 1;
    for (int i = 1; i < n; i++) {
        // for each step, add the last two values and update cur and last
        long tmp = cur;
        cur = cur + last;
        last = tmp;
    }
    return cur;
}

这不仅通过良好的共享减少了代码量,而且在时间上给出了O(n)的复杂度,并且在空间中给出了O(1)的复杂度,而在存储所有中间值时,时间和空间中的O(n)相反..

但是,因为即使这种long类型也会随着n方法100 快速溢出,O(n)的空间复杂性并不是真正的问题,所以你也可以选择这个更容易阅读的解决方案.

public static long possForStep(int n) {
    long[] values = new long[n+1];
    for (int i = 0; i <= n; i++) {
        // 1 for n==0 and n==1, else values[i-1] + values[i-2];
        values[i] = (i <= 1) ?  1 : values[i-1] + values[i-2];
    }
    return values[n];
}

更新:请注意,这与Fibonacci序列接近但不完全相同,而斐波纳契序列0, 1, 1, 2, 3,...在此过程中开始1, 1, 2, 3, 5, ...,即possForStep(n) == fibonacci(n+1).