17

我似乎无法想出一个算法来解决以下问题，我尝试使用一系列 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值，但知道如何使用更大的值肯定会很好。

4

5 回答 5

28

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

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

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

编辑：我假设您会n在这个问题中处理相对较小的值，但如果您处理较大的值，那么上述方法可能需要很长时间才能完成。一种解决方案是使用Map将映射n到的 a 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。第二种方法实际上比第一种方法快几个数量级。

于 2012-09-03T23:53:46.177 回答
8

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

此外，由于 step 的可能性n数量仅取决于 stepn-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 ) .

然而，由于即使类型会在接近 100long时快速溢出，所以O(n)的空间复杂度并不是真正的问题，所以你也可以使用这个更容易阅读的解决方案。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];
}

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

于 2012-09-08T13:59:33.533 回答
1

我会使用动态编程，每次都解决梯子短 1 级或 2 级的问题。

def solveLadder(numOfRungs):
  if numOfRungs<=2:
    return numOfRungs
  return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2)
于 2012-09-03T23:55:33.760 回答
0

这是斐波那契数列。您可以使用尾递归递归优雅地解决它：

    let ladder n =
        let rec aux n1 n2 n =
            if n=0 then (n1 + n2)
            else aux n2 (n1+n2) (n-1)
        aux 1 1 (n-2)

更容易理解的非尾递归代码是：

    let rec ladder n =
        if n<=2 then n
        else ladder (n-1) + ladder (n-2)

您可以轻松地将其转换为 Java。

于 2014-10-19T14:10:53.390 回答
-3
  1. 项目清单

这是一个简单的斐波那契数列，如果我们可以采取的步数是 1 或 2

  • 楼梯数量

    1------------------1

    2-----------------2

    3-----------------3

    4-----------------5

    5-----------------8

    6-----------------13

等等

于 2016-09-08T14:01:58.343 回答