algorithm - 计算至少拿一根棍子的方法

Question

有 N 根木棍排成一条直线。鲍勃打算拿走一些这些棍子。但无论他要拿多少根棍子，他都不会连续拿两根棍子。(即，如果他拿 i 根棍子，他就不会拿 i-1 和 i+1 根棍子。)

因此，给定 N，我们需要计算他可以选择多少组不同的棍子。他至少需要拿一根棍子。

示例:设 N=3，则答案为 4。

4 组是:(1, 3), (1), (2), (3)

主要问题是我想要比简单递归更好的解决方案。它们可以有任何公式吗？因为我无法破解它

Answer 1

它与斐波那契数列几乎相同。最终的解决方案实际上是fibonacci(N)-1，但让我们用实际的棒来解释它。

首先我们忽略了他需要至少拿起一根棍子的事实。本例的解决方案如下:

1. 如果N = 0，则有 1 个解决方案(他拿起 0 根棍子的解决方案)
2. 如果 N = 1，则有 2 个解决方案(拿起棍子，或不拿起棍子)
3. 否则他可以选择
   1. 拿起第一根棍子并在 N-2 上递归(因为需要丢弃第二根棍子)，或者
   2. 离开第一根棍子并在N-1上递归

计算完成后，我们将结果去掉1，以避免计算他总共拿起0根棍子的情况。

伪代码的最终解决方案:

int numSticks(int N) {
    return N == 0 ? 1
         : N == 1 ? 2
         : numSticks(N-2) + numSticks(N-1);
}

solution = numSticks(X) - 1;

如您所见，numSticks 实际上是斐波那契数，可以是 solved efficiently使用例如内存。