回文を形成するための最小挿入数を見つける C プログラム

回文は、その逆に等しい文字列です。文字列が与えられた場合、その文字列を回文にするために必要な、挿入される任意の文字の最小数を見つける必要があります。 3 つのアプローチを見ていきます。最初は再帰的アプローチ、次にこのソリューションをメモ化し、最後に動的プログラミング アプローチを実装します。

再帰的メソッド

例

時間と空間の複雑さ

挿入ごとに選択を行うため、上記のコードの時間計算量は O(2^N) です。N は指定された文字列のサイズです。

上記のコードの空間計算量は O(N) です。つまり、再帰呼び出しで使用されます。

記憶方法

例

時間と空間の複雑さ

計算結果を保存するため、上記のコードの時間計算量は O(N^2) です。

ここでは余分なスペースを使用しているため、上記のコードのスペース複雑さは O(N^2) です。

動的プログラミング手法

例

時間と空間の複雑さ

ここではネストされた for ループを使用しているため、上記のコードの時間計算量は O(N^2) です。

ここでは余分なスペースを使用しているため、上記のコードのスペース複雑さは O(N^2) です。

このチュートリアルでは、特定の文字列を回文にするために必要な最小挿入数を見つける 3 つのメソッドを実装しました。再帰的メソッドを実装し、それをメモ化しました。最後に、表形式手法または動的プログラミング手法を実装しました。

以上が回文を形成するための最小挿入数を見つける C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。