计算梯子上可能的路径数

我似乎无法想出一个算法来解决以下问题，我尝试使用一系列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值，但是如果你处理大问题，那么上面的方法可能需要很长时间才能完成。 一种解决方案是使用将n映射到countPossibilities(n)的Map – 这样，就没有浪费时间去做你已经完成的计算。 像这样的东西：

 private static Map map = new HashMap(); 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 0, 1, 1, 2, 3,...而这一序列分别为1,1,2,3,5 1, 1, 2, 3, 5, ... ，即possForStep(n) == fibonacci(n+1) 。

Answer 3

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

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

Answer 4

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

Answer 5

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

  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。

Answer 6

1. 项目清单

这是简单的斐波纳契系列，如果我们可以采取的步骤是1或2

• 没有楼梯可能的情况

  1 —————— 1

  2 —————— 2

  3 —————— 3

  4 —————— 5

  5 —————— 8

  6 —————— 13

等等