dungeon-game

题目描述

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

题解

动态规划

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    //dp[i][j] 表示从 dp[i][j] 到达 目的地 时最少需要的 HP，应该从右下角推到左上角
    //dp[i][j] = max(1， min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
    int row = dungeon.size();
    int col = dungeon[0].size();
    int** dp = new int* [row];
    for (int i = 0; i < row; i++) {
        dp[i] = new int[col];
    }
    dp[row - 1][col - 1] = max(1, 1- dungeon[row - 1][col - 1]);
    for (int i = row-2; i >= 0; i--) {
        dp[i][col-1] = max(1, dp[i + 1][col-1] - dungeon[i][col-1]);
    }
    for (int j = col-2; j >= 0; j--) {
        dp[row-1][j] = max(1, dp[row-1][j + 1] - dungeon[row-1][j]);
    }
    for (int i = row - 2; i >=0; i--) {
        for (int j = col - 2; j >=0; j--) {
            dp[i][j]= max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
        }
    }

    //print the dp
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return dp[0][0];
}