。奇妙なプリンター

664。奇妙なプリンター

難易度: 難しい

トピック: 文字列、動的プログラミング

次の 2 つの特殊なプロパティを持つ奇妙なプリンターがあります:

• プリンタは毎回、同じ文字のシーケンスのみを印刷できます。
• プリンターは各ターンで、任意の場所で開始および終了する新しい文字を印刷でき、元の既存の文字をカバーします。

文字列 s を指定すると、それを印刷するためにプリンターが必要とする最小回転数を返します。

例 1:

• 入力: s = "aaabbb"
• 出力: 2
• 説明: 最初に「aaa」を出力し、次に「bbb」を出力します。

例 2:

• 入力: s = "aba"
• 出力: 2
• 説明: 最初に「aaa」を出力し、次に文字列の 2 番目の位置から「b」を出力します。これにより、既存の文字 'a' がカバーされます。

制約:

• 1
• s は英小文字で構成されます。

解決策:

動的プログラミングを使用できます。このアイデアは、文字列をサブ問題に分割することで、文字列の出力に必要なターン数を最小限に抑えることです。

この問題は動的計画法を使用して解決できます。アイデアは、問題を小さなサブ問題に分割し、そこで s のすべての部分文字列を出力するために必要な最小ターンを決定することです。次の観察を活用できます:

• 隣接する 2 つの文字が同じ場合、新しい操作としてカウントする代わりに、前の操作を拡張できます。

動的プログラミング ソリューション

dp[i][j] を、部分文字列 s[i:j+1] を出力するために必要な最小ターン数とします。

1. s[i] == s[j] の場合、最後の文字 s[j] は前の操作で出力できるため、dp[i][j] = dp[i][j-1] となります。
2. それ以外の場合、すべての i

このソリューションを PHP で実装してみましょう: 664。奇妙なプリンター

<?php
// Test the function with the given examples
echo strangePrinter("aaabbb") . "\n"; // Output: 2
echo strangePrinter("aba") . "\n";    // Output: 2
?>

説明：

1. DP 配列: 2D 配列 dp[i][j] は、インデックス i から j までの部分文字列を出力するために必要な最小ターン数を表します。

2. 初期化: 1 文字は 1 ターンで印刷できるため、dp[i][i] = 1 と初期​​化します。

3. DP テーブルの入力:

   • i と j の文字が同じである場合 ($s[$i] == $s[$j])、i から j までの印刷には、i から j-1 までの印刷と同じターン数がかかります。 $s[$j] は $s[$i] と同じターンに印刷できるため。
   • それらが異なる場合は、文字列を異なる点 (k) で分割して、最小の巻き数を見つけようとします。

4. 結果: 文字列全体を出力するために必要な最小ターン数は dp[0][$n - 1] に格納されます。

このソリューションは、文字列を分割して出力するすべての可能な方法を考慮して、文字列の出力に必要な最小ターン数を効率的に計算します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。奇妙なプリンターの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。