JavaScriptで2Dグリッドの一意のパスの数を見つける方法

問題の概要

m × n のサイズを持つ2次元配列（グリッド）を想定してみましょう。ある人はこのグリッドの左上のマス (0, 0) からスタートし、右下のゴール地点へ到達することを目指しています。

ただし、移動には制限があります。1回の移動で選べるのは「1マス下へ進む」か「1マス右へ進む」のどちらか一方だけです。

私たちの課題は、グリッドの高さ（行数）と幅（列数）を引数として受け取り、スタートからゴールまで到達できる「一意のパス（経路）」の総数を計算するJavaScript関数を作成することです。

アプローチ：動的計画法

この問題は動的計画法（DP）を使うことで効率的に解けます。ポイントは、任意のマスに到達できるパスの数が「真上のマスに到達できるパスの数」と「真左のマスに到達できるパスの数」の合計になるという性質です。

また、最上行と最左列のマスには、まっすぐ進むしかないため必ず1通りのパスでしか到達できません。これらのセルには初期値として1を設定します。

コード例

以下が実装コードです −

const height = 3;
const width = 4;
const findUniquePath = (width = 1, height = 1) => {
    // 高さ × 幅 の盤面を0で初期化
    const board = Array(height).fill(null).map(() => {
        return Array(width).fill(0);
    });
    // 最上行と最左列はパスが1通りなので1を設定
    for (let rowIndex = 0; rowIndex < height; rowIndex += 1) {
        for (let columnIndex = 0; columnIndex < width; columnIndex += 1) {
            if (rowIndex === 0 || columnIndex === 0) {
                board[rowIndex][columnIndex] = 1;
            }
        }
    }
    // 各マスのパス数 = 上のマスのパス数 + 左のマスのパス数
    for (let rowIndex = 1; rowIndex < height; rowIndex += 1) {
        for (let columnIndex = 1; columnIndex < width; columnIndex += 1) {
            const uniquesFromTop = board[rowIndex - 1][columnIndex];
            const uniquesFromLeft = board[rowIndex][columnIndex - 1];
            board[rowIndex][columnIndex] = uniquesFromTop + uniquesFromLeft;
        }
    }
    // 右下のマスの値が答えとなる
    return board[height - 1][width - 1];
};
console.log(findUniquePath(width, height));

出力結果

コンソールには以下のように出力されます −

10

処理の流れと解説

このコードでは、まず board という2次元配列を作成し、すべてのセルを0で初期化しています。続いて、最上行と最左列のセルに1を設定した後、残りのセルについて「上からのパス数 + 左からのパス数」を順番に計算していきます。

最終的に、右下のゴール地点のセルに格納された値が、スタートからゴールまでの一意のパスの総数となります。この例では、高さ3・幅4のグリッドに対して合計10通りの経路が存在することがわかります。

この手法の時間計算量は O(m × n)、空間計算量も O(m × n) です。すべての経路を実際に辿って数え上げる再帰的なアプローチでは指数時間かかるため、動的計画法による解法が圧倒的に効率的である点が重要です。