計算建構良好弦樂的方法

2466。計算建構良好弦樂的方法

難度：中

主題：動態規劃

給定整數零、一、低和高，我們可以從空字串開始建構一個字串，然後在每一步執行以下任一操作：

• 將字元「0」附加零次。
• 追加字元「1」一次。

此操作可以執行任意多次。

good字串是由上述過程建構的字串，其長度在低和高之間（包含）。

傳回可以建構滿足這些屬性的不同好字串的數量。由於答案可能很大，因此回傳模 10⁹ 7.

範例1：

• 輸入：低= 3，高= 3，零= 1，一= 1
• 輸出： 8
• 說明：
  • 一個可能的有效好字串是「011」。
  • 它可以構造如下："" -> “0”-> “01”-> “011”。
  • 本例中從「000」到「111」的所有二進位字串都是好的字串。

範例2：

• 輸入：低= 2，高= 3，零= 1，一= 2
• 輸出： 5
• 解釋： 好的字串是「00」、「11」、「000」、「110」和「011」。

約束：

• 1 5
• 1

提示：

1. 計算長度小於或等於某個常數x的好字串的數量。
2. 使用連續零和一的群組大小來應用動態規劃。

解：

我們需要專注於建構不同長度的字串並統計滿足給定條件的有效字串的數量。讓我們分解一下方法：

問題分解

1. 狀態定義：
   讓 dp[i] 表示可以使用提供的零和一值建構的長度為 i 的有效字串的數量。

2. 遞迴關係：

   • 對於任意長度 i，我們可以附加：
     • 零個連續的 0，因此前一個字串的長度將是 i-0，我們將新增 dp[i-zero] 方式。
     • 連續一個 1，因此前一個字串的長度將為 i-one，我們將添加 dp[i-one] 方式。

遞推關係變成：
dp[i] = dp[i - 0] dpi - 1

1. 基本情況：

   • 建構空字串的方法只有一種：dp[0] = 1。

2. 最終計算：

   • 長度在low和high之間的有效字串總數是所有i從low到high的dp[i]總和。

解決步驟

1. 初始化一個大小為高1的dp數組，其中每個索引i代表長度為i的有效字串的數量。
2. 從 1 到 high 迴圈遍歷每個可能的長度 i，根據遞推關係更新 dp[i]。
3. 從低到高計算dp[i]的總和，得到最終結果。

讓我們用 PHP 實作這個解決方案：2466。計算建構良好弦樂的方法

<?php
function countGoodStrings($low, $high, $zero, $one) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$low = 3;
$high = 3;
$zero = 1;
$one = 1;
echo countGoodStrings($low, $high, $zero, $one); // Output: 8

$low = 2;
$high = 3;
$zero = 1;
$one = 2;
echo countGoodStrings($low, $high, $zero, $one); // Output: 5
?>

解釋：

1. 初始化：我們先設定基本情況 dp[0] = 1，這表示有一種方法可以形成長度為 0 的字串（空字串）。
2. 動態程式更新： 對於從 1 到高的每個可能的字串長度 i，我們檢查是否可以將長度為零或一的字串附加到較小的字串。我們透過加入形成長度為i-0 和i-1 的字串的方式數來相應地更新dp[i]，確保結果取模10⁹ 7 .
3. 最終結果計算： 我們將 i 在 [low, high] 範圍內的 dp[i] 的所有值相加，得到有效字串的最終計數。

時間複雜度：

• 填滿 dp 陣列需要 O(high)。
• 將低值和高值之間的有效結果相加需要 O(high - low 1)。

因此，整體時間複雜度為 ** O(high) **，這對於輸入限製而言足夠高效。

空間複雜度：

• 我們使用大小為 high 1 的陣列 dp，因此空間複雜度為 O(high).

這個解決方案有效地解決了約束範圍內的問題。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是計算建構良好弦樂的方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！