動的計画法で碁盤の目の左上から右下への道順を数える

動的計画法 (DP)問題 136

碁盤の目の町を、右か下へ 1 マスずつだけ進んで左上から右下へ行く道順が何通りあるかを数えます。上と左のマスの答えを足して表を埋める、2 次元の動的計画の入口の練習です。

海外で定番の問題リスト 4 本には入っていません

問題

縦 rows マス、横 cols マスの碁盤の目の町があります。配達の人は左上のマスから出発し、右か下へ 1 マスずつだけ進んで、右下のマスへ行きます。道順が何通りあるかを返す関数を書いてください。

左や上へは戻れません。斜めにも進めません
通るマスの並びが違えば、別の道順として数えます
rows と cols は 1 以上 100 以下の整数で、答えは 2 × 10^9 以下になるものとします

入力と出力の例

例 1

右へ 3 回、下へ 2 回、合わせて 5 回進みます。5 回のうちどの 2 回を下にするかで、10 通りです。

rows = 3 cols = 4

例 2

右、下の順と、下、右の順の 2 通りです。

rows = 2 cols = 2

例 3

縦が 1 マスなら、右へまっすぐ進む 1 通りしかありません。

rows = 1 cols = 5

面接での聞かれ方

面接では、2 次元の表を埋める動的計画の最初の 1 問として出されます。

「右か下にしか進めないとき、左上から右下への道は何通りありますか」
書き終えると「表を 1 行分の並びに減らせますか？」と続きます
数学の得意な人には「式 1 つで出せますか？」と聞かれることもあります (組み合わせの数で出せます)

続けて「通れないマスがあったら？」と決まりを足されることも多いので、表で埋める書き方を先に身につけておきます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 1

道順を全部たどる再帰は、マスごとに右か下かを選ぶので、道の長さに対して指数的に増えます。100 × 100 では終わりません。

段 2

あるマスへ来る直前は、上のマスから下へ来たか、左のマスから右へ来たかのどちらかです。なので、そのマスへの道順の数は「上のマスへの数」と「左のマスへの数」を足した数です。

段 3

いちばん上の行のマスは、左からまっすぐ来るしかないので、どれも 1 通りです。いちばん左の列も同じく 1 通りです。そこから左上から右下へ、上と左を足して表を埋めます。答えは右下のマスです。

段 4

1 行ずつ埋めるとき、使うのは 1 つ上の行と、同じ行のすぐ左だけです。横 cols 個の並び 1 本を上から書き換えていけば、row[c] += row[c-1] の 1 行で「上 (書き換える前の自分) + 左」になります。

解答

Python

def grid_paths(rows, cols):
    row = [1] * cols
    for _ in range(rows - 1):
        for c in range(1, cols):
            row[c] += row[c - 1]
    return row[cols - 1]

JavaScript

function gridPaths(rows, cols) {
  const m = rows;
  const n = cols;
  const row = Array(n).fill(1);
  for (let r = 1; r < m; r++) {
    let c = 1;
    while (c < n) {
      row[c] += row[c - 1];
      c++;
    }
  }
  return row[n - 1];
}

Go

func gridPaths(
	rows, cols int,
) int {
	row := make([]int, cols)
	for c := range row {
		row[c] = 1
	}
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			row[c] += row[c-1]
		}
	}
	return row[cols-1]
}

始めの row は、いちばん上の行です (どれも 1)。2 行目からは、左端の row[0] は 1 のまま変えず、c が 1 から右へ順に、上 (書き換える前の row[c]) と左 (もう書き換えた row[c-1]) を足します。JavaScript の m と n は、行と列の数を短い名前で持ち直しただけです。

計算量

時間は O(rows × cols) です。表のマスを 1 つずつ埋めます
使う記憶は O(cols) です。持つのは 1 行分の並びだけです
下へ進む回数 rows - 1 を、全部の回数 rows + cols - 2 から選ぶ組み合わせの数として、式で O(rows + cols) で出すこともできます。ただし途中の掛け算が大きくなるので、割り算の順を気にする必要があります

よくある間違い

マスの数と進む回数を取り違える。 3 × 4 の町で進むのは右へ 3 回、下へ 2 回です。右へ 4 回、下へ 3 回と数えると 35 になってしまいます
端の行と列を 0 で始める。いちばん上の行やいちばん左の列を 0 にすると、表の全部が 0 になります。端は 1 通りです
並び 1 本にしたとき、右から左へ埋める。右から埋めると、左のマスがまだ前の行の値のままで、上 + 左にならず答えがずれます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def grid_paths(rows: int, cols: int) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(grid_paths(3, 4))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します