グリッド経路数 (Unique Paths)｜コードで実践

グリッド経路数 (Unique Paths)

このレッスンで分かること

グリッド経路数は 「漸化式 = 数え上げ」 という DP の本質を体感できる問題

時間計算量は O(m * n)、空間計算量は二次元 DP で O(m * n)、1 次元圧縮で O(n)、二項係数を直接計算する数式版で O(min(m, n)) です

m x n の格子マスの左上 (0, 0) から右下 (m - 1, n - 1) まで、右または下にしか進めないという制約の下で、可能な経路は何通りあるでしょうか

グリッド経路数とは

右と下にのみ進めるグリッドの上で、左上から右下に至る経路の総数を二次元 DP で数えます。本レッスンでは、グリッド経路数の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。

m x n の格子マスの左上 (0, 0) から右下 (m - 1, n - 1) まで、右または下にしか進めないという制約の下で、可能な経路は何通りあるでしょうか。例えば 3 x 7 のグリッドなら答えは 28 です。これは古典的な 動的計画法 の入門問題で、組合せ論 と密接に関係します。

直感的には「右に n - 1 歩、下に m - 1 歩」という、合計 (m - 1) + (n - 1) 回の移動の 並び順 の数なので、二項係数 C(m + n - 2, m - 1) でも答えが出ます。ただし本レッスンでは DP の感覚を養うため、表を埋める形で解きます。

グリッド経路数は 「漸化式 = 数え上げ」 という DP の本質を体感できる問題。

状態の定義

dp[i][j] を「(0, 0) から (i, j) までの経路数」とします。(i, j) にたどり着くには、左 (i, j - 1) か上 (i - 1, j) から来るしかありません。よって dp[i][j] = dp[i - 1][j] + dp[i][j - 1] です。

境界条件は 最上行 と 最左列 がすべて 1 です。なぜなら、右しか進めない / 下しか進めない一本道しかないからです。

図解

diagram (will load when visible)

図のポイント (テキスト併記)

セル (i, j) は「上から」または「左から」の 2 通りの経路数を加算することで決まります

セル (i, j) は「上から」または「左から」の 2 通りの経路数を加算することで決まります。これはパスカルの三角形と同じ構造です。

Python 実装

Python

def uniquePaths(m, n):
    dp = [[1] * n for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    return dp[m - 1][n - 1]

配列全体を 1 で初期化しておけば、0 行目と 0 列目の境界処理が一発で済みます。あとは 1 行 1 列目から二重ループで埋めるだけです。

JavaScript 実装

JavaScript

function uniquePaths(m, n) {
  const dp = Array.from({ length: m }, () => new Array(n).fill(1));
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

空間 O(n) に圧縮

二次元 DP の更新で「上 + 左」の値しか使わないことに気づくと、1 次元配列 だけで十分とわかります。

Python

def uniquePaths(m, n):
    dp = [1] * n
    for i in range(1, m):
        for j in range(1, n):
            dp[j] = dp[j] + dp[j - 1]
    return dp[n - 1]

dp[j] が「上 (i - 1, j)」の値、dp[j - 1] が「左 (i, j - 1)」の値です。配列を上書きしながら進められます。

二次元 DP は 「上の行をどれだけ覚える必要があるか」 が分かれば 1 次元に圧縮できる。これは超頻出テクニック。

よくある間違い

1 つ目は 境界初期化忘れ。最上行と最左列を 1 で埋めないと、0 のままで全ての経路数が 0 になります。1 初期化しておくのが安全です。2 つ目は インデックスのオフ・バイ・ワン。m と n を逆にすると、結果は同じ (対称なので) ですが、m x n の意味を混同しないこと。3 つ目は 大きい m、n でのオーバーフロー。Java や C では int で扱うと m + n が大きいとき溢れる可能性があります。Python と JavaScript は気にしなくて OK ですが、Java は long を使うのが安全です。

計算量

時間計算量は O(m * n)、空間計算量は二次元 DP で O(m * n)、1 次元圧縮で O(n)、二項係数を直接計算する数式版で O(min(m, n)) です。経路数の問題は最終的には組合せ数 なので、C(m + n - 2, m - 1) で求めるのが最速です。ただし、表を埋める DP の練習として手で書き下すのは学びが多いです。

同じ問題でも 異なる解法 (DP / 数式 / 分割統治) で書けると、状況に応じて最適な手段を選べる。

やってみよう

3 x 7 の答え 28 を、二項係数 C(8, 2) = 28 で検算する。
1 x 1 の答えは何か？スタートとゴールが同じなので 1 通り。
一部のマスを「通行不可」にした拡張問題 (Unique Paths II) も解いてみる。grid[i][j] == 1 のセルでは dp[i][j] = 0 にするだけ。
経路数だけでなく 実際の経路 を 1 本復元する版にも挑戦する。dp 表を右下から左上へ辿りながら復元するのが鉄板。

経路数 DP は 「漸化式と数え上げの対応」 を理解する最高の練習。組合せ論と DP の橋渡しとして覚えておこう。

よくある質問

Q. この内容は面接でよく聞かれますか？

A. コーディング面接の頻出範囲です。データ構造（リンクリスト・ツリー・グラフ）とアルゴリズム（DP・BFS/DFS）は IT 系大手の選考でほぼ確実に問われます。LeetCode の Top 100 にも該当問題が多数含まれます。

Q. 計算量と空間計算量はどっちを優先しますか？

A. 通常は時間計算量を優先し、空間が制約条件として明示されたら空間も考慮します。例えば「O(1) 空間で」と書かれていれば in-place アルゴリズム必須です。実務では時間 vs メモリのトレードオフを意識しつつ、ボトルネックを実測してから判断します。

Q. 問題が解けないときどう取り組めば良いですか？

A. まず小さな入力（n=3 程度）で手計算し、規則性を見つけます。次にナイーブ解（O(n²) でも可）を書き、最後に最適化します。いきなり最適解を狙うと手が止まりやすいので、段階的に進めるのが定石です。

次のレッスン

次は 単語分割可能か (Word Break) で、右と下にのみ進めるグリッドの上で、左上から右下に至る経路の総数を二次元 DP で数えますを学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

グリッド経路数の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. グリッド経路数とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

グリッド経路数 (Unique Paths)