JavaScriptで2次元配列の合計が最小となるパスを求める方法

問題概要

数値の2次元配列を第1引数（かつ唯一の引数）として受け取るJavaScript関数を考えます。

この関数の目的は、各行からちょうど1つの要素を選んで「パス（経路）」を構成し、その際に隣り合う行から選んだ要素が同じ列にならないようにすることです。そして、条件を満たすすべてのパスの中から、合計値が最小となるものを見つけ、その合計を返します。

例えば、次のような入力が与えられたとします。

const arr = [
    [4, 7, 1],
    [2, 8, 3],
    [5, 6, 9]
]

このとき、期待される出力は次のとおりです。

const output = 9;

出力の解説

条件を満たすパスは、以下の12通り存在します。

これらすべての合計を比較すると、[1, 2, 6] の合計である 9 が最小となります。これが求める答えです。

実装例

この問題を解くコードは次のようになります。

const arr = [
    [4, 7, 1],
    [2, 8, 3],
    [5, 6, 9]
]
const minimumPathSum = (arr = []) => {
    let first = [0, null];
    let second = [0, null];
    for(let row = arr.length - 1; row >= 0; row--){
        let curr1 = null;
        let curr2 = null;
        for(let column = 0; column < arr[row].length; column++){
            let currentSum = arr[row][column];
            if(column !== first[1]){
                currentSum += first[0];
            }else{
                currentSum += second[0];
            };
            if(curr1 === null || currentSum < curr1[0]){
                curr2 = curr1;
                curr1 = [currentSum, column];
            }else if(curr2 === null || currentSum < curr2[0]){
                curr2 = [currentSum, column];
            };
        };
        first = curr1;
        second = curr2;
    };
    return first[0];
};
console.log(minimumPathSum(arr));

アルゴリズムのポイント

この実装では動的計画法（DP）の考え方を用いています。配列の末尾の行から先頭へ向かって処理を進め、各時点で「現在の最小合計」と「二番目に小さい合計」（およびそれらがどの列由来か）を記録していきます。

同じ列を連続して選べないという制約があるため、直前行の最小値が今注目している列と一致する場合は、代わりに二番目に小さい値を採用します。このように最小値と準最小値の2つだけを保持すればよいので、各行の更新処理は列数に比例する計算量で完了します。

その結果、全体の時間計算量は O(行数 × 列数) となり、すべての経路を実際に列挙する指数時間のアプローチに比べて、はるかに効率的に答えを導き出せます。

出力結果

コンソールには次のように出力されます。

9