動的計画法：小問題から状態・遷移・初期条件を設計する

1．「同じ続きをもう一度考える」をやめる

6段の階段を、一度に1段または3段ずつ上るとします。上り方をすべて書くと、途中で同じ段に着く方法が何度も現れます。到着までの履歴が違っても、以後に使える歩幅は同じです。そこで「この段まで来る方法は何通りだったか」を付箋に書いておけば、毎回最初から数え直す必要がなくなります。ここでの1回の移動を一歩と呼び、順序が違う歩幅の列は別の上り方と数えます。階段を上り過ぎたり、下りたりはしません。

動的計画法（DP）は、大きな問題を小問題に分け、小問題の答えを保存して再利用する方法です。単に表を作るのではなく、表のマスの意味と、ほかのマスから答えを作る根拠を設計します。既習の計算量の比較から一歩進み、本記事では公式を与えられる前に「どんな小問題を解けばよいか」を考えます。以下の数値設定はすべて学習用の自作例で、測定値や実際の通貨制度を表すものではありません。

2．状態は「答えを記録する小問題の住所」

階段全体の答えをいきなり求める代わりに、0段、1段、2段までならどうかを考えましょう。状態を段の番号 i とし、表の値 f(i) を「0段目からちょうど i 段目に着く歩幅の列の個数」と定めます。状態 i は住所、f(i) はそこに保存する答えです。i は0以上の整数で単位は段、f(i) の単位は通りです。「i段以下に着く個数」ではない点も定義の一部です。

3．遷移は「最後の一歩」で分ける

i段目に着いた上り方を、最後の一歩だけ取り外してみます。最後が1段なら直前は i−1 段目、最後が3段なら直前は i−3 段目です。これ以外の最後の一歩はなく、同じ上り方が両方に属することもありません。また、直前までの上り方に最後の一歩を付ければ元に戻せます。この「漏れなし・重なりなし・元に戻せる」が、個数を足してよい理由です。小問題から別の小問題の値を作る関係を遷移と呼びます。

4．初期条件は、公式の外ではなく意味から決める

0段目には、何もしない空の歩幅の列が1通りあります。だから f(0)=1 です。負の段に着く上り方はないので、式を統一して書くため f(i)=0（i<0）と約束します。これは実在する地下の階段を追加するという意味ではありません。これらの境界の値を先に定め、1段目から順に計算すれば、右辺はすべて既に分かっています。

5．最適化では、足す代わりに最良の候補を選ぶ

次は架空の1点・3点・4点の券を何枚でも使い、合計をちょうど a 点にする問題です。上り方を数えるのではなく、券の枚数を最少にしたいとします。大きい券から取ればよさそうですが、6点では4+1+1の3枚より3+3の2枚が少なくなります。目先の選択だけで決める貪欲法が、この券の組では失敗する例です。

m(a) を「ちょうど a 点を作る最少枚数」と定めます。最後に使う券の点数 c が分かれば、残りは a−c 点です。残りに最少でない作り方を使っているなら、より少ない枚数の作り方に取り替えられ、全体も改善します。したがって各 c について m(a−c)+1 を候補にし、一番小さい値を取れば十分です。このように最適な解の中に小問題の最適な解を使える性質を、最適部分構造と呼びます。

a は0以上の整数の点数、m(a) は枚数です。空の支払いには0枚必要なので m(0)=0 とします。使える券が別の組で、ある点数が作れない場合は、到達不能を +∞ として区別します。候補が空のときの最小値も +∞ と定め、+∞+1=+∞ と扱えば、作れない候補を誤って採用しません。実装では無限大の値か、到達不能を示す別の印を使います。

6．情報を忘れすぎたら、状態を増やす

付箋を小さくするために、未来の選択に必要な情報まで捨ててはいけません。階段に「3段の一歩を連続して使ってはいけない」という追加条件があると、同じ段に着いても直前が1段か3段かで次に使える歩幅が変わります。一歩ずつ延長する遷移では、各段までの総数 f(i) だけでは、そこから3段進める列の個数が分かりません。A(i)を最後が1段の個数、B(i)を最後が3段の個数と分けると、必要な情報を残せます。出発点では便宜上 A(0)=1、B(0)=0 とし、負の添字は0とします。A(0)は実際に1段上った意味ではなく、最初のどちらの歩幅も許す空の履歴です。

最後が1段なら、その前はどちらでもよいので足します。最後が3段なら、その前が3段のものは除くので A だけを使います。求める個数は A(i)+B(i) です。状態をまとめてよいかは「まとめた履歴同士で、今後の合法な選択と、その後の評価が同じか」を点検して判断します。最適化なら、捨てた候補が今後逆転しないことも必要です。

7．一度しか使えない品物では、どこまで見たかも状態にする

各品物が1個ずつしかない買い物では、残り容量が同じでも、使える品物が違えば続きを同じには扱えません。品物に順番を付け、D(i,w) を「最初の i 個から、重さの合計が w kg 以下になるよう選ぶときの最大価値（点）」と定義します。各重さと容量は非負の整数kgで、品物の重さは正、価値は非負とします。何も選ばないことを許し、品物は分割できません。これが0/1ナップザック問題の一つの設定です。

aᵢ は i 番目の品物の重さ（kg）、vᵢ は価値（点）です。最後の品物を「選ばない」か「選ぶ」かの2候補を比べます。選ぶ場合はその重さを容量から引き、価値を足します。どちらも前の行 i−1 から読むので、同じ品物を再び使うことはありません。ここでは「容量以下」なので D(0,w)=0 がすべての w≥0 で正しい初期値です。「ちょうど w kg」に変えるなら、品物0個で正の重さは作れず、この初期値は使えません。

8．計算順と正しさを一緒に点検する

机に小問題のカードを並べ、あるカードの答えに必要なカードから矢印を引くと、計算順が見えます。階段と券では添字が必ず小さくなり、ナップザックでは品物数が一つ減るため、依存関係に循環がありません。先に必要なカードを計算して表を埋める方法がボトムアップです。求める答えから再帰的に必要な小問題へ下り、計算済みの答えを保存するメモ化再帰も同じ遷移を使えます。ただし保存するだけで循環する依存関係が解消するわけではありません。

1. 状態の意味：表のマスが答える小問題を一文で述べる。必要な履歴や制限を忘れていないか。
2. 初期条件：空の選択・容量0・到達不能の値を、個数や最小値などの意味から決める。
3. 遷移の根拠：最後の選択で漏れなく分ける。数え上げなら重複がなく、最適化なら残りを最適なものに置き換えられるか。
4. 計算順：参照する値が既に確定している順に進める。各小問題が正しいと仮定して遷移先も正しいことを示せば、初期条件から帰納的に全体が正しい。
5. 出力と検算：全体の答えがどのマスか確認する。小さい入力を全列挙し、表の値と比べる。

計算量はおおむね「状態数×1状態の候補数」です。n段の階段は O(n)、目標T点・券がk種類の最少枚数は O(Tk)、N個・容量Wのナップザックは O(NW) 回の基本演算で求まります。素直に表を保存する領域は順に O(n)、O(T)、O(NW) です。ここでは整数の加算・比較を一定時間と数えています。大きな個数を正確に保持する場合は桁数による演算費用や整数の範囲にも注意します。またWは数値そのものなので、二進表記の入力長に対する多項式時間を O(NW) が保証するわけではありません。状態が多すぎる問題では、DPでも計算は重くなります。