例如:
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
任何人都可以提供有关如何完成此操作的伪代码的提示。 老实说,甚至不知道如何开始。 这看起来像一个指数问题,它可以在线性时间内完成吗?
谢谢。
最佳答案
在您提供的示例中,加数的顺序很重要。 (请参阅示例中的最后两行)。考虑到这一点,答案似乎与斐波那契数列有关。假设 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)
关于c++ - 给定一个整数 n,返回它可以表示为 1 和 2 之和的方式的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40062774/