動的計画法では、小さな問題の答えを保存しておき、後の選択で再利用できるようにします。まず、1つの状態が何を意味するかを書き出してください。経路の数、最小コスト、到達できるかどうかを示すフラグは、ループが似て見えても、それぞれ異なる初期値が必要です。0はコストとしては有効ですが、後の経路の初期値になる空の経路の数としては有効ではありません。
依存関係から反復の順序を決めてください。繰り返し使えるトークンは、小さい合計を何度でも伸ばせます。分割できない木箱はそうはいきません:部分和を下へ向かって更新すれば、その木箱を2回使うことを防げます。狭義単調増加部分列では、最良の末尾を集めたコンパクトな集合が、2乗サイズの状態の表の代わりになります。
コーディングの前に、空でない最小の入力と空の入力をたどってください。コーディングの後に、すべての遷移が正当な選択を表している理由と、どの選択も失われない理由を説明してください。最後の練習問題では、状態の考え方を経路の数ではなく荷物の分け方に適用します。