1. 概要

このチュートリアルでは、最長のパリンドロームサブシーケンスの問題について説明します。

まず、いくつかの基本的な定義で問題を説明します。 次に、いくつかのシーケンス例とそれぞれの最長のパリンドロームサブシーケンスを示します。

最後に、トップダウンとボトムアップの動的計画法のアプローチについて説明します。

目前の問題に飛び込む前に動的計画法の基本についてもっと学ぶために、他のいくつかのチュートリアルもチェックすることをお勧めします。 ナップサックまたは最長増加部分列は、基本的な動的計画法の問題であり、簡単に始めることができます。

2. 定義

まず、問題を正しく理解し、いくつかの定義を与えましょう。

  1. サブシーケンス：要素の配列から取得されたサブシーケンスは、元のシーケンスからいくつかの（場合によってはゼロの）要素を削除することによって取得されるシーケンスです。 つまり、取得した要素の相対的な順序を変更せずに、元のシーケンスから取得したシーケンスです。 たとえば、bdfはabcdefgのサブシーケンスです。 また、xyzは同じxyzシーケンスのサブシーケンスであると見なします。 ただし、元のシーケンスでaとbの順序を変更したため、abdはbaedのサブシーケンスではありません。
  2. 回文：回文は、同じ順方向と逆方向に読み取ることができる任意のシーケンスです。 たとえば、abcbaとbyzzybはパリンドロームシーケンスですが、abcaはそうではありません。

したがって、説明した問題は簡単に定義できます。一連の要素が与えられた場合、私たちのタスクは、回文である最長のサブシーケンスの長さを見つけることです。

3. 例

さまざまなシーケンスの例と、それぞれの最長のパリンドロームサブシーケンスを示す表を見てください。

この問題では、最長のパリンドロームサブシーケンスの長さにのみ関心があります。 したがって、パリンドロームのサブシーケンスがいくつ見つかってもかまいません。

4. 動的計画法アプローチ

動的計画法ソリューションを構築するには、問題をより小さなサブ問題に分割する必要があります。 各サブ問題を状態と呼びます。 サブ問題の答えを組み合わせることで、完全な問題の答えに到達できます。

現在の問題のサブ問題について考えてみましょう。 完全な問題は、完全なシーケンスに対する答えを見つける必要があります。 サブ問題については、元のシーケンスから特定の範囲に対する答えを見つけます。

このタイプのサブ問題を選択する理由は3つあります。

最初の理由は、基本サブ問題が2つのオプションのうちの1つであるということです。 長さ1の範囲に対する答えを計算する必要がある場合、その答えは1に等しくなります。 これは、長さ1のシーケンスが回文であるためです。 それ以外の場合、空の範囲に到達すると、その答えはゼロになります。

2番目の理由は、パリンドロームシーケンスの最初と最後の要素が等しいことです。 これらの要素を削除した場合、残りの要素もパリンドロームシーケンスを形成する必要があります。 したがって、状態から、最初の要素とn th要素が等しい場合に状態に移行できます。

最後の理由は、最初と最後の要素が等しくない場合です。 この場合、2つのオプションがあります。 最初の要素または最後の要素のいずれかを削除することで最良の答えを見つけることができます。 たとえば、状態から、first要素とn th 要素が等しくない場合、範囲またはのいずれかで最良の答えを見つけることができます。

説明したアプローチのアルゴリズムを実装するために、トップダウンアプローチとボトムアップアプローチの2種類の動的計画法があります。 それぞれを詳しく見ていきましょう。

4.1. トップダウンアプローチ

トップダウンアプローチは通常、理解しやすいです。 各ステップで、アルゴリズムをすべてのサブ問題に再帰的に適用します。 その後、サブ問題の回答に基づいて現在の問題の回答を計算します 。

問題をサブ問題に分割する前に、現在の状態がの前に計算されているかどうかを確認します。 もしそうなら、私たちは計算された答えを返すだけです。 それ以外の場合は、再帰呼び出しを行います。

説明されているアプローチの擬似コードを見てください。 最初の呼び出しでは、配列に-1の値を入力する必要があります。これは、まだ状態を計算していないことを示します。 また、1に等しく、に等しいシーケンスを渡す必要があります。ここで、はシーケンスの長さです。

ご覧のとおり、基本サブ問題に到達した場合は、その回答を返します。 また、以前にこの状態を計算したことがある場合は、その答えを返します。

それ以外の場合、範囲の両側が等しい要素を保持している場合、サブ問題から取得できる最良の答えを計算します。 その後、パリンドロームのサブシーケンスにL th要素とRth 要素を含めたため、現在の状態の回答に2を追加します。

L th要素とRth 要素が等しくない場合、2つのオプションがあります。 1つ前に移動することも、1つ後ろに移動することもできます。 最終的な答えは、2つのオプション間の最大値です。 後で同じ状態に達した場合に再利用できるように、回答を配列内に格納していることに注意してください。

上記のアプローチの時間計算量はです。ここで、はシーケンスの長さです。 その理由は、各状態を1回だけ計算するためです。 したがって、配列がいっぱいになると、それ以上計算を行わずにすぐに答えが返されます。

4.2. ボトムアップアプローチ

ボトムアップアプローチでは、小さなサブ問題に対する答えを計算してから、大きなサブ問題に移動します。

簡単にするために、状態を少し変更します。 から始まり、長さが。の範囲の回答を格納する状態を検討します。 擬似コードを見てみましょう。

まず、2つの基本的なサブ問題に対する答えを保存します。 次に、可能なすべての長さを繰り返します。 小さなサブ問題から始めて大きなサブ問題に到達する必要があるため、長さを昇順で繰り返すことに注意してください。

範囲の両端が一致する場合、長さを2増やした後、次の要素に移動します。 それ以外の場合、両端が一致しない場合は、からまたはから始まる小さい範囲の回答を確認します。 その後、これら両方のオプション間の最大値を保存します。 最後に、完全な問題に対する答えがに保存されます。

ボトムアップアプローチの複雑さもです。ここで、はシーケンスの長さであり、トップダウンの複雑さと同様です。

5. 結論

このチュートリアルでは、最長のパリンドロームサブシーケンスの問題について説明しました。 また、その問題の例をいくつか示しました。 最後に、問題を解決するためのトップダウンおよびボトムアップの動的計画法のアプローチと、各アプローチの複雑さを示しました。