我似乎无法想出解决以下问题的算法,我尝试使用一系列 for 循环,但它变得太复杂了:
A ladder has
n
steps, 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?
例如,如果梯子有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
值,但知道如何处理较大的值肯定会很好。
最佳答案
有趣的是,这个问题有一个简单的解决方案。您可以使用递归:
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
。第二种方法实际上比第一种方法快几个数量级。
关于java - 计算梯子上可能的路径数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12255193/