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

Count number of possible paths up ladder

提问by arshajii

I can't seem to come up with an algorithm to solve the following problem, I tried using a series of for-loops but it became way too complicated:

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

A ladder has nsteps, 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?

梯子是有n台阶的，可以任意组合1阶或2阶的任意组合爬上梯子。有多少种可能的方式可以爬上梯子？

So for example, if the ladder had 3 steps, these would be the possible paths:

因此，例如，如果梯子有3 个步骤，则这些将是可能的路径：

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

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

And for 4 steps

而对于4 个步骤

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

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

Any insight as to how this could be done would be greatly appreciated. Also, I'm working in Java.

任何有关如何做到这一点的见解将不胜感激。另外，我正在使用 Java。

Edit: I was indeed going to be using small nvalues, but it certainly would be neat to know how to manage with larger ones.

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

回答by arshajii

Interestingly, there is a simple solution to this problem. You can use recursion:

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

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

Whenever you're faced with this type of "tricky" problem, bear in mind that the solution is often times quite elegant, and always check to see if something can be done with recursion.

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

EDIT: I was assuming that you would deal with relatively small nvalues in this problem, but if you deal with large ones then the method above will probably take a good amount of time to finish. One solution would be to use a Mapthat would map nto countPossibilities(n)- this way, there would be no time wasted doing a computation that you've already done. Something like this:

编辑：我假设您将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;
}

Try this with n = 1000. The second method is literally orders of magnitude faster than the first one.

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

回答by tobias_k

This is in fact closely related to the Fibonacci sequence, as was mentioned only briefly in one of the comments so far: Each step ncan be reached from either two steps below (n-2) or one step below (n-1), thus the number of possibilities to reach that step is the sum of the possibilities to reach those other two steps. Finally, there is exactly one possibility to reach the first step (and the zeroth, i.e. staying on the ground).

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

Also, as the number of possibilities for step ndepends only on the results for step n-1and n-2, it is not necessary to store all those intermediate values in a map or in an array -- the last two are enough!

此外，由于 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;
}

This not only reduces the amount of code by a good share, but also gives a complexity of O(n)in time and O(1)in space, as opposed to O(n)in time andspace when storing all the intermediate values.

这不仅通过良好的份额减少的代码量，而且还给出了一个复杂为O（n）在时间和O（1）在空间中，而不是为O（n）在时间和存储所有的中间值时，空间.

However, since even the longtype will quickly overflow as napproaches 100 anyway, space complexity of O(n)is not really a problem, so you can just as well go with this solution, which is much easier to read.

然而，即使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];
}

Update:Note that this is close to, but not quite the same as the Fibonacci sequence, which starts 0, 1, 1, 2, 3,...while this one goes 1, 1, 2, 3, 5, ..., i.e. possForStep(n) == fibonacci(n+1).

更新：请注意，这是接近，但不完全一样的斐波那契序列，开始0, 1, 1, 2, 3,...而这一去1, 1, 2, 3, 5, ...，即possForStep(n) == fibonacci(n+1)。

回答by ajon

I would use dynamic programming and each time solve a problem where the ladder is 1 rung or 2 rungs shorter.

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

def solveLadder(numOfRungs):
  if numOfRungs<=2:
    return numOfRungs
  return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2)

回答by duffymo

It's a tree with recursion. You might need to backtrack for those cases that can't work (e.g. 2-2 for a three stair ladder).

这是一棵递归树。对于那些无法工作的情况，您可能需要回溯（例如，对于三层楼梯，2-2）。

回答by SpaceMonkey

This is the fibonacci series. You can solve it elegantly using tail recursive recursion:

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

    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)

An easier to understand non-tail recursive code would be:

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

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

You can easily translate that to Java.

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

回答by Sanjay Das

1. List item

1. 项目清单

This is simple fibonacci series if the no of step we can take is 1 or 2 for

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

• No of stair possible case

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

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

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

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

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

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

• 没有楼梯可能的情况

  1---1

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

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

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

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

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

and so on

等等