给定一个整数n，返回它可以表示为1和2的和的方式的数量 [英] Given an integer n, return the number of ways it can be represented as a sum of 1s and 2s

问题描述

例如：

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

任何人都可以给出伪码的提示，请做。
老实说没有线索如何开始。
这也看起来像一个指数问题，可以在线性时间吗？

Can anyone give a hint for a pseudo code on how this can be done please. Honestly have no clue how to even start. Also this looks like an exponential problem can it be done in linear time?

感谢您。

推荐答案

的加数很重要。 （请参见示例中的最后两行）。考虑到这一点，答案似乎与斐波纳契数字有关。让我们 F（n）是方式 n 可以写为1s和2s。那么最后加法是1或2.因此 F（n）= F（n-1）+ F（n-2）。这些是初始值：

In the example you have provided order of addends is important. (See the last two lines in your example). With this in mind, the answer seems to be related to Fibonacci numbers. Let's F(n) be the ways n can be written as 1s and 2s. Then the last addened is either 1 or 2. So F(n) = F(n-1) + F(n-2). These are the initial values:

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

这篇关于给定一个整数n，返回它可以表示为1和2的和的方式的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！