c++ - 给定一个整数 n，返回它可以表示为 1 和 2 之和的方式的数量

Question

例如:

5 = 1+1+1+1+1

5 = 1+1+1+2

5 = 1+1+2+1

5 = 1+2+1+1

5 = 2+1+1+1


5 = 1+2+2

5 = 2+2+1

5 = 2+1+2

任何人都可以提供有关如何完成此操作的伪代码的提示。老实说，甚至不知道如何开始。这看起来像一个指数问题，它可以在线性时间内完成吗？

谢谢。

Answer 1

在您提供的示例中，加数的顺序很重要。 (请参阅示例中的最后两行)。考虑到这一点，答案似乎与斐波那契数列有关。假设 F(n) 是 n 可以写成 1 和 2 的方式。然后最后添加的是 1 或 2。所以 F(n) = F(n-1) + F(n-2)。这些是初始值:

F(1) = 1 (1 = 1)
F(2) = 2 (2 = 1 + 1, 2 = 2)