読者です 読者をやめる 読者になる 読者になる

動的計画法を使ってグリッドの経路数を求める

AtCoder メモ化 動的計画法 漸化式 2次元配列

問題

C: 経路 - AtCoder Beginner Contest 034 | AtCoder

100点解法

※この問題は101点満点なので、満点解法ではない。

動的計画法を用いて経路数を算出する。 動的計画法を用いることができるのは以下の2つのポイントをおさえているから。

  1. 分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く
  2. メモ化: 部分問題の計算結果を保存し、再利用する

上記のポイントをこの問題に当てはめてみる。

分割統治法: 部分問題を解き、その計算結果を用いて全体問題を解く

今回は、座標が(W, H)までの経路数を求めたい。座標(W, H)の1つ前の座標を考えてみると、右か上にしか進めないので考えられる座標は(W - 1, H), (W, H -1)の2点となる。そして、座標(W, H)までの行き方はこの2通りしかないので、(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)が必要な時に再計算せずに保存した値を再利用する。これによって計算量を減らす事ができる。

以上を考慮して動的計画法を実装すると以下になる。

ソースコード