给定整数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可以写为1S和2S.然后最后一次加注是1或2.所以F(n) = F(n-1) + F(n-2).这些是初始值:

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