什么是不连续 1 的二进制字符串的 Count 个数？

让我们考虑一个例子来解释计算没有连续 1 的二进制字符串的概念。

例子

假设我们要统计长度为3且不包含连续1的二进制字符串的数量。二进制字符串是仅由 0 和 1 组成的字符串。

长度为 3 的可能二进制字符串为：000、001、010、011、100、101、110 和 111。

但是，我们只需要计算那些没有连续 1 的二进制字符串。因此，我们需要从计数中排除字符串 011、101 和 111。

我们来分析一下剩下的二进制字符串：

• 000：这是一个有效的字符串，因为它没有连续的 1。

• 001：这是一个有效的字符串，因为它没有连续的 1。

• 010：这是一个有效的字符串，因为它没有连续的 1。

• 100：这是一个有效的字符串，因为它没有连续的 1。

• 110：这是一个无效字符串，因为它有连续的 1。

从上面的分析可以看出，长度为3的有效二进制串有4个，且没有连续的1。

PHP 程序计算没有连续 1 的二进制字符串的数量

方法1-使用动态规划

例子

输出

Number of binary strings without consecutive 1's: 13

代码说明

此 PHP 代码定义了一个名为 countBinaryStrings 的函数，该函数使用动态编程计算长度为 $n 且不包含连续 1 的二进制字符串的数量。它使用基本情况 $dp[0] = 1 和 $dp[1] = 2 初始化数组 $dp，表示字符串的计数长度分别为0和1。然后，它使用循环通过对长度 $i - 1 和 $i - 的计数求和来填充长度 2 到 $n 的剩余计数。 2. 最后，它返回长度 $n 的计数并打印它。在此特定示例中，代码计算长度为 5 且没有连续 1 的二进制字符串的数量并显示结果。

方法2

输出

Number of binary strings without consecutive 1's: 13

代码说明

此 PHP 代码计算长度为 $n 且不含两个连续 1 的不同二进制字符串的数量。它定义了两个数组，$a 和 $b，来存储计数。基本情况设置为 $a[0] = $b[0] = 1。然后，使用循环计算长度 1 到 $ 的计数n-1。长度 $i 的计数是通过将数组 $a 中的长度 $i-1 的计数与长度 $[ 的计数相加而获得的&&&]i-1 来自数组 $b。另外，数组 $b 中长度 $i 的计数是从数组 $ 中长度 $i-1 的计数获得的一个。最后，代码返回数组 $a 中长度 $n-1 的计数与数组 $n-1 长度的计数之和&&&]$b，表示不连续1的二进制串总数。在此特定示例中，代码计算长度为 5 的计数并显示结果。 结论

总之，第一种方法利用动态编程，用基本情况初始化数组并迭代计算较大长度的计数。它通过将前两个长度的计数相加来有效地计算结果。第二种方法采用更简单的方法，使用两个数组来存储计数，并根据先前长度的计数迭代更新它们。它直接计算总计数，无需分别对两个数组求和。这两种方法都可以对没有连续 1 的二进制字符串进行精确计数，并且它们之间的选择可能取决于具体要求和性能考虑。