2次元の状態は、物理的な位置や、消費した2つの接頭辞を表すことがよくあります。グリッドのセルは隣のセルに依存します。文字列の接頭辞の長さの組は、どの編集やインターリーブがまだ可能かを表します。表のレイアウトを選ぶ前に、両方の座標に名前を付けてください。1行分を使い回して空間を節約できるのは、すべての依存関係が正しい古い行または新しい行を参照し続けている場合だけです。
境界の状態が、仕事の多くを担います。ふさがったセルは経路の数を消し、空の接頭辞にも意味のある編集コストがあり、繰り返す文字があると有効なインターリーブが複数残ることがあります。貪欲に一致させると、後で必要になる経路を捨ててしまうことがあります。
最後の問題では、状態の形が区間に変わります。区間の中で最後に取り除くものを選ぶと、その隣が確定し、残りの作業は独立した左右の部分に分かれます。考え方は同じです:次の判断が明確に定まる状態を選び、小さい依存関係から先に処理します。