グリッド経路数
左上から右下まで「右」と「下」だけで進む道順が何通りあるかを、マスに通り数を書き込みながら数えます。
4
5
0
計算中
上から
左から
壁（クリックで設置）
—
格子状の道で、左上スタートから右下ゴールまで 右か下にだけ進みます。道順は何通り？
全部の道を 1 本ずつ数えると組合せ爆発しますが、DP なら各マスに「そのマスに着く道順の数」を書き込むだけ。
あるマスへは 真上のマスから来るか 左のマスから来るかのどちらか。だから
全部の道を 1 本ずつ数えると組合せ爆発しますが、DP なら各マスに「そのマスに着く道順の数」を書き込むだけ。
あるマスへは 真上のマスから来るか 左のマスから来るかのどちらか。だから
そのマス = 上のマス + 左のマス。マスをクリックすると通行止め（壁）を置けます。
いま計算しているマス
ここが DP の本質
- 「ゴールまでの道順」という大きな問いを、「各マスまでの道順」という小さな問いに分ける。
- 各マスは すぐ上と左の答えを足すだけ。一度数えたマスは二度と数え直さない。
- 壁を置くと、そのマスは 0 通り。下流のマスへ自動的に波及するのが DP の強み。