TopCoder からこの問題を解決したいと思います。この問題では、文字列が指定され、各ステップで、(選択した) 文字のすべての発生を (選択した) 別の文字に置き換える必要があります。回文を取得する手順。問題は、置換の最小総数を特定することです。
これまでのアイデア: 各ステップの後の文字列はグラフの単なるノード/頂点であり、各エッジのコストはステップで行われた置換の数であることを識別できますが、欲張りを使用する方法がわかりませんそれは (最小スパニング ツリーの問題ではないことは間違いありません)。考えられるすべてのノードとエッジ コストを特定し、問題を最短経路問題に変換することは意味がないと思います。反対に、すべてのステップで、文字 X を最大数の競合に置き換え、文字 Y を文字列内で最も多く発生する X と競合するように置き換えることは理にかなっていると思います。
とにかく、それが機能することを証明することもできません。また、これで既知の問題を特定できません。何か案は？