计算上梯的可能路径数

小编典典

计算上梯的可能路径数

algorithm

我似乎无法提出一种算法来解决以下问题，我尝试使用一系列的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值，但是知道如何使用较大的值进行管理当然很整洁。

阅读 256

2020-07-28

共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。第二种方法实际上比第一种快几个数量级。

2020-07-28