Unique Paths

ロボットが右下のセルに入る最後の移動について考えてみましょう。ロボットは、上のセルから下に移動するか、左のセルから右に移動するかのどちらかで、両方ではありません。したがって、m × n のグリッドを通る経路は、1行少ないグリッドを通る経路 uniquePaths(m-1, n) と、1列少ないグリッドを通る経路 uniquePaths(m, n-1) の合計です。

グリッドが1行または1列になると再帰は終了します。この場合、ロボットはまっすぐ進むことしかできないため、経路はちょうど1つです。すべての経路は2つの移動のうちどちらか一方で終わるので、それぞれの経路は1回だけ数えられ、合計は正しくなります。

各経路は、1を返す基本ケースに到達するため、呼び出し回数は少なくとも答えの数だけになります。そのため処理が遅くなります。17 × 17 のグリッドでは6億回を超える呼び出しが必要で、テストでは答えが約1.6 × 10^9に近い値まで扱われます。同じ小さなグリッドが何度も計算されます。(m-1, n-1) には2つの親それぞれから1回ずつ到達し、下に進むにつれて重複が増えていきます。

再帰では同じセルを何度も調べますが、セルは全部で m × n 個しかありません。必要なセルが常に計算済みになっている順序で、各セルに至る経路数を一度だけ数えましょう。

状態： paths[r][c] は、左上のセルから行 r、列 c までの経路数です。 漸化式： paths[r][c] = paths[r-1][c] + paths[r][c-1]。上から来る経路と、左から来る経路を足します。 基底ケース： 最上行と最左列の各セルには、一直線の経路が1つあります。 順序： 行ごとに左から右へ進みます。こうすれば、必要になる前に上のセルと左のセルが計算済みになります。

m = 3、n = 4 の場合、各行は 1 1 1 1、次に 1 2 3 4、最後に 1 3 6 10 となり、答えは最後のセルの10です。

次に、計算時に参照するものを見てみましょう。参照するのは、直上の行と計算中の行だけです。そこで、1行だけ保持します。 row[c] を更新する前は、まだ直上の行の経路数が入っています。また、row[c-1] には左隣の新しい経路数がすでに入っているので、row[c] += row[c-1] だけで漸化式をそのまま計算できます。時間計算量は O(m × n) のままで、メモリ使用量は O(m × n) から O(n) に減ります。

すべての経路は、下に進む移動をちょうど m-1 回、右に進む移動をちょうど n-1 回、合計で m+n-2 回、何らかの順序で行います。どの順序も有効な経路です。ロボットが下に m-1 回より多く進んだり、右に n-1 回より多く進んだりすることはないため、グリッドから出ることはありません。したがって、経路は m+n-2 回の移動のうち、どの m-1 回を下に進む移動にするかを選ぶことと同じで、答えは二項係数 C(m+n-2, m-1) です。

前の方法で使った表は、パスカルの三角形を横向きにしたものなので、2つの方法で同じ結果になります。巨大な階乗を使わずに係数を計算するには、因子を1つずつ掛けていきます。N = m+n-2、k = min(m, n)-1 として、i が1から k までの各ステップで、N-k+i を掛けてから i で割ります。ステップ i の後の累積値は C(N-k+i, i) という整数になるため、毎回割り切れます。

m = 3、n = 4 の場合、N = 5、k = 2 となり、値は 1 × 4 / 1 = 4、続いて 4 × 5 / 2 = 10 と変化します。短い方の辺に沿って選ぶことで、ループは最大99ステップになります。最後の除算の前の積は、答えの k 倍です。17 × 17 のグリッドでは、16 × 601,080,390、つまり約 9.6 × 10^9 となり、32ビットの範囲を超えるため、64ビット整数に格納してください。