C++で解くダンジョンゲーム：最小初期体力を求める動的計画法

問題概要

悪魔たちが王女Pを捕らえ、ダンジョンの右下の部屋に閉じ込めてしまった――そんな物語を想像してみてください。ダンジョンはM行N列の格子状に並ぶ部屋で構成されており、勇敢な騎士Kは左上の部屋から出発し、戦いながら王女を救い出すために進まなければなりません。

騎士には正の整数で表される初期体力（HP）があります。移動中のどの時点でも体力が0以下に落ちれば、その瞬間に命を落としてしまいます。

一部の部屋には悪魔が待ち構えており、そこに入ると体力が減少します（負の整数として表現）。一方、空の部屋や魔法のオーブが置かれた部屋に入ると、体力は回復します（正の整数として表現）。

王女のもとへ一刻も早くたどり着くため、騎士は各ステップで「右」か「下」のどちらかにのみ進むことにしました。ここでの目的は、王女にたどり着くうえで十分となる最小の初期体力を求めることです。

入力例

この入力に対する答えは6です。騎士が「右 → 右 → 下 → 下」の経路を選べば、初期体力6で最後まで生き延び、王女Pにたどり着けるためです。

解法の考え方（動的計画法）

この問題は、右下（ゴール）から左上（スタート）へ向かって値を遡りながら更新していく動的計画法（DP）で解けます。具体的な手順は次のとおりです。

• r を dp の行数、c を dp の列数とします。
• j を r-2 から 0 まで 1 ずつ減らしながら処理します。
  • dp[j, c-1] := min(dp[j, c-1], dp[j, c-1] + dp[j+1, c-1])
• j を c-2 から 0 まで 1 ずつ減らしながら処理します。
  • dp[r-1, j] := min(dp[r-1, j], dp[r-1, j] + dp[r-1, j+1])
• i を r-2 から 0 まで減らし、その内側で j を c-2 から 0 まで減らしながら二重ループを実行します。
  • dp[i, j] := min(dp[i, j], max(dp[i, j] + dp[i+1, j], dp[i, j] + dp[i, j+1]))
• dp[0, 0] が 0 以下の場合は、|dp[0, 0]| + 1 を返します。
• そうでなければ 1 を返します。

計算量は時間・空間ともに O(M×N) であり、グリッドのサイズに対して効率的に求解できます。

C++による実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli min(lli a, lli b){
    return a <= b ? a : b;
}
lli max(lli a, lli b){
    return a <= b ? b : a;
}
class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dp) {
        int r = dp.size();
        int c = dp[0].size();
        for(lli j=r-2;j>=0;j--){
            dp[j][c-1] = min(dp[j][c-1], dp[j][c-1]+dp[j+1][c-1]);
        }
        for(lli j = c-2;j>=0;j--){
            dp[r-1][j] =min(dp[r-1][j], dp[r-1][j]+dp[r-1][j+1]);
        }
        for(lli i = r-2;i>=0;i--){
            for(lli j = c-2;j>=0;j--){
                dp[i][j] = min(dp[i][j],max(dp[i][j]+dp[i+1][j],dp[i][j]+dp[i][j+1]));
            }
        }
        if(dp[0][0] <= 0 )return abs(dp[0][0])+1;
        return 1;
    }
};
main(){
    Solution ob;
    vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
    cout << (ob.calculateMinimumHP(v));
}

入力

{{-2,-2,3},{-5,-10,1},{10,30,-5}}

出力

6