我似乎无法想出一个算法来解决以下问题,我尝试使用一系列for循环,但它变得太复杂了:
梯子有
n
台阶,人们可以使用1步或2步的任意组合爬上梯子。有多少可能的方式爬梯子?
因此,例如,如果梯子有3个步骤,这些将是可能的路径:
并为4个步骤
任何关于如何做到这一点的见解将不胜感激。另外,我在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
。第二种方法比第一种方法快几个数量级。
这实际上与Fibonacci sequence密切相关,正如在迄今为止的评论中仅简要提到的那样:每个步骤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,...
,而这个序列为1, 1, 2, 3, 5, ...
,即possForStep(n) == fibonacci(n+1)
。
我会使用动态编程,每次解决梯子1档或2档较短的问题。
def solveLadder(numOfRungs):
if numOfRungs<=2:
return numOfRungs
return solveLadder(numOfRungs-1)+solveLadder(numOfRungs-2)
这是一棵带递归的树。对于那些无法工作的情况,您可能需要回溯(例如,对于三个阶梯,2-2)。
这是斐波那契系列。您可以使用尾递归递归优雅地解决它:
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。
这是简单的斐波那契系列,如果我们可以采取的步骤是1或2
等等