文字列の問題の多くは二つのテキストを比較するか一つのテキストを部分に分けるもので、どちらも同じ形をしています:接頭辞、または接頭辞の組に対する答えは、少しだけ短い接頭辞に依存します。cell[i][j]を一方の文字列の先頭i文字ともう一方の先頭j文字に対する答えと定義し、セルが隣のセルからどう求まるかを書き、テーブルを一行ずつ埋めてください。
二つの文字列では、一致する文字の組は対角線のセルを延ばし、不一致ならどちらかの文字列の文字を飛ばしたうちの良いほうを取ります。一つの文字列を分ける場合、ok[end]やways[end]は最後の部分が始まりうるすべての位置をさかのぼって調べます。数え上げの問題では各選択肢からの方法の数を足し、最適化の問題では最小値か最大値を取ります。
面接で時間を節約できる習慣が二つあります。コードを書く前に一つのセルが何を意味するかを一文で述べ、基底の行を決めてください:空の接頭辞は通常、方法がちょうど一通りか、コストがゼロです。各行が前の行だけを必要とするなら、二行だけ保持すれば空間はO(nm)からO(m)に減ります。