确定可能有多少个不同的数组

Question

假设我们有一个长度为X的布尔数组。唯一的规则是，TRUE不能在相邻的地方出现两次。特别是允许仅具有错误值的数组。例如。这是禁止的：[1,1,0,0,0]并允许这些：[1,0,0,0,0]，[0,0,0,0,0]，[1,0,1 ，0,1]等。如何使用动态编程来确定有多少个不同长度为X的有效数组？

Answer 1

设Ti是满足您的标准并以1结尾的长度为i的数组的数量，并且让Fi为满足您的标准并且不以1结尾的长度为i的数组的数量。

然后：

• 0 = 0
• F0 = 1
• Ti + 1 = Fi。 （满足你的标准并以1结尾的每个长度为i + 1的数组由一个长度为i的数组组成，它符合你的标准，并且不以1结尾，加上最后的额外1。）
• Fi + 1 = Fi + Ti。 （满足您的标准且不以1结尾的每个长度为i + 1的数组由满足您标准的长度i的数组组成，最后加上额外的0。）
• 你想要FX + TX。

因此，您只需编写一个循环，计算从0到X的每个i的Fi和Ti，然后返回FX + TX。

（这甚至不是动态编程本身，因为你不需要存储部分值; Fi + 1和Ti + 1仅依赖于Fi和Ti。所以这是O（X）时间和O（1）空间。）

Answer 2

我想你可以在不使用DP的情况下计算数字。因为你知道长度为N的数组总数，即'2 ^ N'。

现在你需要扣除那些没有资格的bad阵列，如果他们有相邻的1。对于长度为N的数组，存在这些情况

1. the array has no 1's, only one case, and it is a valid array
2. the array has one 1's, all cases are valid
3. the array has two 1's, there are N - 1 cases which are not valid
4. the array has three 1's, there are (N-1) * (N-2) / 2 cases which are not valid

...

Answer 3

dp解决方案将具有两个状态参数。一个是数组的位置，另一个是前一个位置的值。如果前一个位置的值为1，那么您只能选择0.如果前一个位置的值为0，那么您可以选择1或0.希望这会有所帮助。

Answer 4

你真的不需要动态编程。对于数组长度X，有效数组的数量是Fib（X + 1），其中Fib是斐波纳契数的数组。

X = 1：有效数组：2

X = 2：有效数组：3

X = 3：有效数组：5

X = 4：有效数组：8

等等...

示范：

假设我们正在寻找X的数组，我们知道X-1的有效数组的数量。我们可以在每个X-1长度数组的末尾自由添加零，所以到目前为止是F（X-1）。我们还可以在每个X-1数组的末尾添加一个'1'，以0结尾。但是这些数组有多少？好吧，它正好是F（X-2），因为我们可以完全相同的方式生成零结束X-1长度数组：通过在每个X-2长度数组的末尾添加零。所以F（X）= F（X-1）+ F（X-2）这正是Fibonacci数组的定义。

我们所要做的就是手动计算前两个元素，以确定它是否完全是Fibonacci数组，还是它被移位。

你甚至可以找到一个公式来计算斐波纳契数组的第N个元素，因此它可以在O（1）中求解。