動的計画法を使ってグリッドの経路数を求める
問題
C: 経路 - AtCoder Beginner Contest 034 | AtCoder
100点解法
※この問題は101点満点なので、満点解法ではない。
動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の２つのポイントをおさえているから。
- 分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く
- メモ化: 部分問題の計算結果を保存し、再利用する
上記のポイントをこの問題に当てはめてみる。
分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く
今回は、座標が(W, H)までの経路数を求めたい。座標(W, H)の１つ前の座標を考えてみると、右か上にしか進めないので考えられる座標は(W - 1, H), (W, H -1)の２点となる。そして、座標(W, H)までの行き方はこの２通りしかないので、(W - 1, H)に辿り着く経路数と(W, H - 1)に辿り着く経路数の和となる。抽象的に言うと、座標(i, j)までの経路数をf(i, j)とすると以下の漸化式が成り立つ
f(i, j) = f(i - 1, j) + f(i, j - 1)
メモ化: 部分問題の計算結果を保存し、再利用する
前述したf(i, j)の値はi, jが小さい値から埋めていくことができ、その埋めた値を使って次の計算を行う事ができる。一度f(i, j)を計算したものを保存しておき、再びf(i, j)が必要な時に再計算せずに保存した値を再利用する。これによって計算量を減らす事ができる。
以上を考慮して動的計画法を実装すると以下になる。
