グリッド経路数 (Unique Paths)

道順を手で数えると、漏れる

碁盤の目のような街を、左上から右下まで歩きます。進めるのは右か下だけ。行き方は何通りあるでしょうか。

2 行 3 列くらいなら、指でなぞって数えられます。3 行 7 列で 28 通り。10 行 10 列だと 4 万 8 千通りを超えます。もう手では数えられませんし、1 本ずつなぞって数える方法はプログラムにしても遅すぎます。同じ道の途中を、別の道の一部として何度もなぞり直すことになるからです。

なぞらずに数える手があります。

上から来た数と、左から来た数を足す

あるマスに立っているとき、そこへ来る直前にいた場所は 2 つしかありません。すぐ上のマスか、すぐ左のマスです。右か下にしか進めないので、それ以外からは来られません。

ということは、そのマスまでの行き方の数は、上のマスまでの行き方の数と、左のマスまでの行き方の数を足したものになります。なぞる必要はなく、足し算だけで進みます。

一番上の行と一番左の列は、どのマスも 1 です。上の行はずっと右に進む一本道、左の列はずっと下に進む一本道しかないからです。

3 行 4 列で、左上から順に埋めてみます。

右下の 10 が答えです。2 行 2 列目の 2 は、上の 1 と左の 1 を足したもの。3 行 3 列目の 6 は、上の 3 と左の 3 を足したものです。パスカルの三角形を斜めに寝かせた形になっています。

表全体を 1 で埋めてから始めると、端の初期化を別に書かなくて済みます。

ここを 0 で作ってしまうと、端が 0 のまま足し算が進み、右下まで 0 のままになります。埋める順番も大事で、上の行から順に、行の中は左から右へ進みます。逆に回すと、まだ埋めていない値を足すことになります。

前の行しか使わない

足すのは「上」と「左」だけで、2 行以上前の値は使いません。ということは、表を丸ごと持たなくても 1 行ぶんの配列で足ります。左から右へ上書きしていくと、まだ書き換えていない位置には上の行の値が、直前に書き換えた位置には左の値が入っているからです。

この「必要な過去だけ持つ」考え方は、前のレッスンの変数 2 つと同じ発想です。まずは表をそのまま作って正しく動かし、動いてから減らすのが安全です。順番を 1 つ間違えるだけで静かに違う答えを返すので、減らす前の版と結果を突き合わせられる状態にしておくと安心です。

なお、行と列を入れ替えても答えは同じです。右に何歩、下に何歩の並べ方を数えているだけなので、どちらが縦でも変わりません。ただし表の大きさは変わるので、m と n を取り違えたまま添字を書くと範囲外になります。

やってみよう

• 3 行 7 列で 28 になることを、表を書いて確かめる
• 1 行 1 列のとき、答えは 1。出発点と目的地が同じマス
• 組合せの式でも出る。3 行 4 列なら右に 3 歩と下に 2 歩の並べ方なので、5 個から 2 個を選ぶ組合せで 10

1. 戻り値は経路の総数 (整数)
2. 右と下にしか移動できない (上や左には戻れない)
3. 二次元 DP もしくは 1 次元圧縮 DP で求めること