良い文字列を構築する方法を数えてみましょう-PHPチュートリアル-php.cn

良い文字列を構築する方法を数えてみましょう

Patricia Arquette

リリース： 2025-01-02 15:13:40

オリジナル

389 人が閲覧しました

Count Ways To Build Good Strings

2466。良い文字列を構築する方法を数えてみましょう

難易度: 中

トピック: 動的プログラミング

整数 0、1、low、high を指定すると、空の文字列から始めて文字列を構築し、各ステップで次のいずれかを実行できます。

文字「0」を 0 回追加します。
文字「1」を 1 回追加します。

これは何度でも実行できます。

良好な文字列は、上記のプロセスによって構築された文字列で、低値と高値の間の長さ (を含む) を持ちます。

これらのプロパティを満たす異なる適切な文字列の数を返します。答えは大きくなる可能性があるため、modulo 10⁹ 7.

を返します。

例 1:

入力: 低 = 3、高 = 3、ゼロ = 1、1 = 1
出力: 8
説明:
- 有効な有効な文字列の 1 つは「011」です。
- 次のように構築できます: "" -> 「0」→ 「01」→＞「011」。
- この例では、「000」から「111」までのすべてのバイナリ文字列が適切な文字列です。

例 2:

入力: 低 = 2、高 = 3、ゼロ = 1、1 = 2
出力: 5
説明: 適切な文字列は、「00」、「11」、「000」、「110」、および「011」です。

制約:

1 105

ヒント:

解決策:

さまざまな長さの文字列を構築し、指定された条件を満たす有効な文字列の数を数えることに焦点を当てる必要があります。アプローチを詳しく見てみましょう:

問題の内訳

状態定義:
dp[i] は、指定された 0 と 1 の値を使用して構築できる長さ i の有効な文字列の数を表します。
再発関係:

漸化関係は次のようになります:

dp[i] = dp[i - ゼロ] dpi - 1

基本ケース:
- 空の文字列を構築する方法は 1 つだけあります: dp[0] = 1。
最終計算:
- 低位から高位までの長さの有効な文字列の総数は、低位から高位までのすべての i の dp[i] の合計です。

解決策のステップ

サイズが高さ 1 の dp 配列を初期化します。ここで、各インデックス i は長さ i の有効な文字列の数を表します。
1 から最大までの各可能な長さ i をループし、漸化関係に基づいて dp[i] を更新します。
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
?>

ログイン後にコピー

説明：

初期化: 基本ケースの dp[0] = 1 を設定することから始めます。これは、長さ 0 の文字列 (空の文字列) を形成する方法が 1 つあることを意味します。
動的プログラミングの更新: 1 から最大までの可能な文字列長 i ごとに、長さ 0 または 1 の文字列をより小さい文字列に追加できるかどうかを確認します。長さ i-0 と i-1 の文字列を形成する方法の数を追加することで dp[i] を更新し、結果が 10⁹ 7.
最終結果の計算: [low, high] の範囲内の i に対する dp[i] のすべての値を合計して、有効な文字列の最終的な数を取得します。

時間計算量:

したがって、全体的な時間計算量は

** O(high) ** となり、入力制限に対して十分に効率的です。

空間の複雑さ: