计算梯子上可能的路径数

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

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

每当您遇到这种类型的“棘手”问题时，请记住，解决方案通常非常优雅，并始终检查是否可以使用递归完成某些操作。

编辑：我假设你会在这个问题上处理相对较小的值，但是如果你处理大的值，那么上面的方法可能需要很长时间才能完成。一种解决方案是使用映射到 - 这样，就不会浪费时间进行您已经完成的计算。像这样：nMapncountPossibilities(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

这实际上与斐波那契数列密切相关，正如到目前为止在其中一条评论中简要提到的那样：每个步骤都可以从下面的两个步骤（）或下面的一个步骤（）到达，因此达到该步骤的可能性数量是达到其他两个步骤的可能性的总和。最后，只有一种可能性可以达到第一步（第零步，即留在地面上）。nn-2n-1

此外，由于步长的可能性数仅取决于步长和 的结果，因此没有必要将所有这些中间值存储在映射或数组中 - 最后两个就足够了！nn-1n-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）。

但是，由于即使类型也会在接近100时迅速溢出，因此O（n）的空间复杂性并不是真正的问题，因此您也可以使用此解决方案，这更容易阅读。longn

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

更新：请注意，这与斐波那契数列接近，但并不完全相同，斐波那契数列从这个序列开始，即。0, 1, 1, 2, 3,...1, 1, 2, 3, 5, ...possForStep(n) == fibonacci(n+1)