Trò chơi ngục (Dungeon Game) trong C++

Kho lưới M×N, mỗi ô có giá trị (âm = quái, dương = hồi máu). Kỵ sĩ bắt đầu (0,0), chỉ đi phải/xuống, cần máu > 0 luôn. Tìm máu ban đầu tối thiểu để cứu công chúa ở (M-1,N-1).

Ví dụ

Đường đi: Phải → Phải → Xuống → Xuống. Máu tối thiểu = 6.

Thuật toán: DP ngược (Bottom-up từ đích)

dp[i][j] = máu tối thiểu cần có khi VÀO ô (i,j) để có thể sống đến đích.

Cơ sở: dp[M-1][N-1] = max(1, 1 - dungeon[M-1][N-1]).

Chuyển trạng thái (từ dưới/lên, phải/trái):

need = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]
dp[i][j] = max(1, need)

Cài đặt 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(), c = dp[0].size();
        // Cột cuối
        for (int j = r-2; j >= 0; j--)
            dp[j][c-1] = min(dp[j][c-1], dp[j][c-1] + dp[j+1][c-1]);
        // Hàng cuối
        for (int j = c-2; j >= 0; j--)
            dp[r-1][j] = min(dp[r-1][j], dp[r-1][j] + dp[r-1][j+1]);
        // Các ô còn lại
        for (int i = r-2; i >= 0; i--)
            for (int 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]));
        return dp[0][0] <= 0 ? abs(dp[0][0]) + 1 : 1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{-2,-2,3},{-5,-10,1},{10,30,-5}};
    cout << ob.calculateMinimumHP(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(M*N).
• Không gian: O(1) thêm (sửa mảng đầu vào) hoặc O(M*N) nếu dùng bảng riêng.

Input / Output

Input:  {{-2,-2,3},{-5,-10,1},{10,30,-5}}
Output: 6