假设我们有一个长度为X的布尔数组。唯一的规则是，TRUE不能在相邻位置出现两次。尤其是只允许使用假值的数组。例如，这是禁止的：[1，1，0，0，0]，这些是允许的：[1,0,0,0]，[0,0,0]、[1,0,1,0,1]等。我如何使用动态编程来确定长度为X的有效数组有多少？
设Ti为满足您的标准并在1中结束的长度为i的数组的数量，设Fi为满足您标准并不在1中终止的长度为i的阵列的数量。
然后：
- T 0=0
- F 0=1
-
T
i+1=Fi。(每个长度i+1且满足您的标准并以
1结尾的数组都包含一个长度i且满足您标准且未以1结尾的数组，以及结尾处的额外1。( -
F
i+1=Fi+Ti。(每个长度i+1且符合您的标准且在
1中未结束的数组由一个长度i且符合您标准的数组组成，加上末尾的额外0。( - 您想要FX+TX
因此，您只需编写一个循环，计算从0到X的每个Fi和Ti，然后返回FX+TX。
(这本身甚至不是动态编程，因为您不需要存储部分值；Fi+1和t<1>仅取决于Fi以及t>i。所以这是O(X(时间和O(1(空间。(
我认为您可以在不使用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
dp解决方案将有两个状态参数。一个是数组的位置，另一个是上一个位置的值。如果上一个位置的值为1，则只能选择0。如果上一个位置的值为0，则可以选择1或0。希望这能有所帮助。
您实际上并不需要动态编程。对于数组长度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(。我们还可以在每个以0结尾的X-1数组的末尾添加一个"1"。但是这些数组有多少？它正好是F(X-2(，因为我们可以用完全相同的方式生成零结尾的X-1长度数组：在每个X-2长度数组的末尾添加一个零。所以F(X(=F(X-1(+F(X-2(这正是斐波那契数组的定义。
我们所要做的就是手动计算前两个元素，以确定它是斐波那契数组还是移位了。
你甚至可以找到一个公式来计算斐波那契数组的第N个元素，所以它可以在O(1(中求解。