寻找在一个 n 级楼梯中向上走的所有方式，如果您每次可以走 k 步，且 k <= n。

Question

寻找在一个 n 级楼梯中向上走的所有方式，如果您每次可以走 k 步，且 k <= n。

5

这是我自己尝试解决的递归问题（不是作业）。我相信我找到了解决方案，但我不确定时间复杂度（我知道DP会给我更好的结果）。

给定n个台阶和每次能上k个台阶，找出所有可以上到n个台阶的方法，其中k <= n。例如，如果我的步幅为[1,2,3]，而楼梯的大小为10，则我可以走10步，每步为1 [1,1,1,1,1,1,1,1,1,1]=10，或者我可以走3步，每步为3，再走1步，每步为1 [3,3,3,1]=10。

以下是我的解决方案：

static List<List<Integer>> problem1Ans = new ArrayList<List<Integer>>();
public static void problem1(int numSteps){
    int [] steps = {1,2,3};
    problem1_rec(new ArrayList<Integer>(), numSteps, steps);
}
public static void problem1_rec(List<Integer> sequence, int numSteps, int [] steps){
    if(problem1_sum_seq(sequence) > numSteps){
        return;
    }
    if(problem1_sum_seq(sequence) == numSteps){
        problem1Ans.add(new ArrayList<Integer>(sequence));
        return;
    }
    for(int stepSize : steps){
        sequence.add(stepSize);
        problem1_rec(sequence, numSteps, steps);
        sequence.remove(sequence.size()-1);
    }
}
public static int problem1_sum_seq(List<Integer> sequence){
    int sum = 0;
    for(int i : sequence){
        sum += i;
    }

    return sum;
}
public static void main(String [] args){
    problem1(10);
    System.out.println(problem1Ans.size());

}

我的猜测是，这个运行时间是 k^n，其中 k 是步长的数量，n 是步数（在这种情况下分别为 3 和 10）。

我得出这个答案的原因是，每个步长都有一个循环，调用 k 个步长。然而，所有步长的深度并不相同。例如，序列 [1,1,1,1,1,1,1,1,1,1] 比 [3,3,3,1] 有更多的递归调用，所以这让我对我的答案产生了怀疑。

运行时间是多少？k^n 正确吗？

- Spark323

1

如果您对复杂度不确定，可以测量不同值的时间并绘制图表。这通常能够给您一个很好的复杂度函数的概念。 - MrSmith42

这个算法的时间复杂度是正确的，至少在最坏情况下是这样。改进它的一种方法是使用记忆化（见链接），基本上是将所有部分解决方案保存在映射中并重用它们。这并不会改善时间复杂度本身，但确实可以提高性能。https://zh.wikipedia.org/wiki/%E8%A8%98%E6%86%B6%E5%8C%96 - Rex Wagenius

1

基本上，对于每个n的值，您都有k个递归情况，因此您拥有的基本上是一个k叉树。现在，最短路径是您执行更大步骤的路径，这些步骤是n // k +（n％k）//（k-1）+（（n％k）/ /（k-1）％（k-1））+ ...，直到达到1。现在，该级别以上的所有节点形成一个完整的k叉树，其中至少有k ^（n // k + ...）个节点。因此，它应该至少接近。 - Bakuriu

我想知道为什么你要存储准确的答案。如果你只获取这些计数，运行时间可以大大降低。这似乎具有O(k^(n/avg(steps)))的复杂度，至少是O(k^(n/max(steps)))，因为大小为N的唯一运行将是仅包含1的运行，但每个运行都将迭代至少(n/max(steps))层k叉树。 - Vesper

@Vesper 只是为了测试一下。我最初打算将解决方案打印出来，但现在只是为了大小而改变了它。 - Spark323

提示：设f(n,k)为爬楼梯的方式数。写出f的递推关系式。千里之行，始于足下。 - Colonel Panic

2个回答

1

如果你想以递归方式解决这个问题，你应该使用一种不同的模式，允许缓存先前的值，就像计算斐波那契数列时使用的模式一样。斐波那契函数的代码基本上与你所寻找的内容相同，它通过索引添加前一个和前前一个数字，并将输出作为当前数字返回。你可以在递归函数中使用相同的技术，但不是添加 f(k-1) 和 f(k-2)，而是收集 f(k-steps[i]) 的总和。类似这样（我没有Java语法检查器，请忍受语法错误）：

static List<Integer> cache = new ArrayList<Integer>;
static List<Integer> storedSteps=null; // if used with same value of steps, don't clear cache
public static Integer problem1(Integer numSteps, List<Integer> steps) {
    if (!ArrayList::equal(steps, storedSteps)) { // check equality data wise, not link wise
        storedSteps=steps; // or copy with whatever method there is
        cache.clear(); // remove all data - now invalid
        // TODO make cache+storedSteps a single structure
    }
    return problem1_rec(numSteps,steps);
}
private static Integer problem1_rec(Integer numSteps, List<Integer> steps) {
    if (0>numSteps) { return 0; }
    if (0==numSteps) { return 1; }
    if (cache.length()>=numSteps+1) { return cache[numSteps] } // cache hit
    Integer acc=0;
    for (Integer i : steps) { acc+=problem1_rec(numSteps-i,steps); }
    cache[numSteps]=acc; // cache miss. Make sure ArrayList supports inserting by index, otherwise use correct type
    return acc;
}

- Vesper

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

你的算法是O(2^n)，这比O(k^n)更紧密，但由于一些容易纠正的低效率，实现的运行时间为O(k^2 × 2^n)。

实际上，您的解决方案通过逐步枚举所有可行前缀的步骤序列来枚举所有和为n的步骤序列。因此，操作次数与其总和小于或等于n的步骤序列数量成比例。[请参见注1和注2]。

现在，让我们考虑对于给定的n值有多少可能的前缀序列。精确的计算将取决于允许步长向量中的步骤，但我们可以很容易地想出一个最大值，因为任何步骤序列都是从1到n的整数集合的子集，而我们知道恰好存在2 ⁿ这样的子集。

当然，并非所有子集都符合条件。例如，如果步长集是[1, 2]，则您正在枚举斐波那契数列，其中有O(φⁿ)个这样的序列。随着k的增加，您将越来越接近O(2ⁿ)。[请参见注3]

由于您的编码效率低下，如前所述，您的算法实际上是O(k² αⁿ)，其中α是介于φ和2之间的某个数字，当k趋近于无穷大时，接近于2。(φ是1.618..., 或 (1+sqrt(5))/2)。

如果您的意图是计数而不是枚举步长，那么可以对您的实现进行许多改进。但我理解您的问题并非如此。

注意事项

这并不完全准确，因为实际上你会列举出一些额外的序列，然后再拒绝它们；这些拒绝的成本是可能步长向量大小的乘数。但是，你可以通过在注意到拒绝时立即终止for循环来轻松消除这些拒绝。
枚举的成本是O(k)，而不是O(1)，因为你为每个枚举计算序列参数的总和（通常是两次）。这产生了一个额外的因子k。你可以通过将当前总和传递给递归调用来轻松消除这个成本（这也会消除多次评估）。更难的是避免复制序列到输出列表的O(k)成本，但是可以使用更好的（结构共享）数据结构来完成。
与你问题主体中代码解决的问题不同，你标题中的问题实际上需要枚举{1…n}的所有可能子集，在这种情况下，可能序列的数量将恰好为2的n次方。