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

Question

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

Answer 1

令 T_i 为满足您的条件且以 1 结尾的长度为 i 的数组的数量, 并令 F_i 为满足您的条件的长度为 i 的数组的数量，并执行 不以 1 结尾。

然后:

• T₀ = 0
• F₀ = 1
• T_i+1 = F_{i。 (每个满足您的标准并以 1 结尾的长度 i+1 的数组都包含满足您的标准但不的长度i 的数组> 以 1 结尾，最后加上额外的 1。)}
• F_i+1 = F_i + T_i。 (每个长度 i+1 的数组满足您的标准并且不以 1 结尾，由一个长度 i 的数组组成，满足您的标准，最后加上一个额外的 0。)
• 你想要F_X + T_X.

所以你可以只写一个循环来计算 F_i 和 T _i 对从 0 到 X 的每个 i，然后返回 F_X + T_X。

(这本身就不是动态规划，因为您不需要存储部分值；F_i+1 和 T_i+1 仅取决于 F_{i/sub> 和 Ti。所以这是 O(X) 时间和 O(1) 个空间。)}