重要な判断が入力を途中で分割するため、左から右へ順に解けない問題もあります。山のマージ、板の切断、列の両端からのカード取り、左右対称になる文字の選択は、どれもstartからendまでの区間での最善の答えを求めるもので、その答えは内側のより小さい区間に依存します。
一つの区間についてbest[start][end]を定義し、それから区間の分け方を選んでください。マージでは、最後のマージが[start, mid]と[mid + 1, end]をつなぎます。切断では、最初の切断で独立した二つの木片が残ります。二人対戦のゲームでは、手番のプレイヤーが端を取り、相手は残りで最善の手を打ちます。最初の操作で自身の隣が変わってしまう場合は、隣が固定されている区間内の最後の操作を代わりに選んでください。
区間を長さの順に短いものから埋めるか、startを右から左へ動かして、内側の区間がすべてそろっているようにしてください。区間がn^2個で、それぞれ最大n通りの分割があるので、時間はO(n^3)、空間はO(n^2)になると見込まれ、数百個の要素なら問題ありません。