什麼是不連續 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 的二進位字串進行精確計數，並且它們之間的選擇可能取決於特定要求和效能考慮。