グリッド上で目的地に到達するために必要な最小の初期ポイント｜動的計画法による解法

あるグリッドの左上のマスからスタートし、右下のマス（ゴール）へ到達することを考えます。グリッドの各マスには整数が書かれており、その値は正の場合も負の場合もあります。人物がマス (i, j) に到達すると、所持しているトークンの数はそのマスに書かれた値の分だけ増加または減少します。本記事では、この旅を完遂するために必要な初期トークンの最小値を求めるアルゴリズムを解説します。

ルール

• 移動できるのは右方向または下方向のみです。
• 所持トークンの合計がマス (i, j) の値より少ない場合、そのマスに入ることはできません。
• ゴールには最小限の正のポイントを持った状態で到達しなければなりません。

入力と出力

入力：
各部屋のトークンを行列として与える。
-2  -3   3
-5 -10   1
10  30  -5

出力：
旅の開始に必要な最小トークン。
この例では、必要なトークンは 7。

この例では、左上の -2 から出発して右下の -5 にたどり着くまでに、途中で -10 といった大きなマイナスのマスを通るため、あらかじめ 7 以上のトークンを持っていないと道中でポイントが不足してしまいます。

アルゴリズム

この問題は動的計画法（DP）を使うことで効率的に解けます。鍵となるのは「ゴール側から逆算する」という発想です。各マスにおいて「そのマスに立った時点で最低いくつのトークンが必要か」を記録するテーブル minToken を、右下から順に埋めていきます。

関数：minInitTokens(matrix)

入力： 各部屋のトークン行列
出力： スタート地点から目的地まで到達するために必要な最小トークン

Begin
    行列と同じサイズの minToken を定義する
    m := 行列の行数
    n := 行列の列数

    if matrix[m-1, n-1] > 0 ならば
        minToken[m-1, n-1] := 1
    else
        minToken[m-1, n-1] := 1 + |matrix[m-1, n-1]|

    // 最終列を下から上へ埋める
    for i := m-2 down to 0, do
        minToken[i, n-1] := max(1, minToken[i+1, n-1] - matrix[i, n-1])
    done

    // 最終行を右から左へ埋める
    for j := n-2 down to 0, do
        minToken[m-1, j] := max(1, minToken[m-1, j+1] - matrix[m-1, j])
    done

    // 残りのセルを右下から左上へ埋める
    for i := m-2 down to 0, do
        for j := n-2 down to 0, do
            rem := min(minToken[i+1, j], minToken[i, j+1])
            minToken[i, j] := max(1, rem - matrix[i, j])
        done
    done

    return minToken[0, 0]
End

アルゴリズムのポイント

• ゴールのマスでは、値が正なら必要ポイントは 1、負なら「絶対値 + 1」となります。
• 各マスでは、進める隣接マス（下 or 右）のうち必要ポイントが小さい方を選び、そこから現在のマスの値を差し引いたものが基準になります。
• 常に最低 1 ポイントは保持しておく必要があるため、max(..., 1) を取ります。

C++ による実装例

#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
    {-2,-3,3},
    {-5,-10,1},
    {10,30,-5}
};

int max(int a, int b) {
    return (a>b)?a:b;
}

int minInitPoints() {
    int minToken[ROW][COL];
    int m = ROW, n = COL;

    // ゴールのマス：正なら 1、負なら絶対値 + 1
    minToken[m-1][n-1] = tokens[m-1][n-1] > 0 ? 1 : abs(tokens[m-1][n-1]) + 1;

    // 最終列を下から上へ埋める
    for (int i = m-2; i >= 0; i--)
        minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);

    // 最終行を右から左へ埋める
    for (int j = n-2; j >= 0; j--)
        minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

    // 残りのセルを右下から左上へ埋める
    for (int i = m-2; i >= 0; i--) {
        for (int j = n-2; j >= 0; j--) {
            int remPoint = min(minToken[i+1][j], minToken[i][j+1]); // 残りポイントを計算
            minToken[i][j] = max(remPoint - tokens[i][j], 1);
        }
    }
    return minToken[0][0];
}

int main() {
    cout << "Minimum Points Required: " << minInitPoints();
}

実行結果

Minimum Points Required: 7

計算量

グリッドの全マスを一度ずつ処理するだけなので、時間計算量・空間計算量はともに O(m × n) です。全経路を探索する総当たり法に比べて格段に効率的であり、大きなグリッドでも高速に答えを求められます。