- int calculateMinimumHP(vector<vector<int>>& dungeon) {
- if (dungeon.size() == 0)
- return 0;
- int end_x = dungeon.size() - 1; // 行
- int end_y = dungeon[0].size() - 1; // 列
- vector<vector<int>> dp(dungeon.size(), vector<int>(dungeon[0].size()));
- if (dungeon[end_x][end_y] <0)
- dp[end_x][end_y] = -dungeon[end_x][end_y];
- else
- dp[end_x][end_y] = 0;
- for (int j = end_y-1; j>= 0; --j) // 对最后一行的每列进行处理
- {
- dp[end_x][j] = dp[end_x][j + 1] - dungeon[end_x][j];
- if (dp[end_x][j] <0)
- dp[end_x][j] = 0;
- }
- for (int i = end_x - 1; i>= 0; --i)
- {
- dp[i][end_y] = dp[i+1][end_y] - dungeon[i][end_y];
- if (dp[i][end_y] <0)
- dp[i][end_y] = 0;
- }
- for (int i = end_x - 1; i>= 0; --i)
- {
- for (int j = end_y - 1; j>= 0; --j)
- {
- dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
- if (dp[i][j] < 0)
- dp[i][j] = 0;
- }
- }
- return dp[0][0] + 1;
- }
动态规划方程
dp[i][j]=max(1,min(dp[i+1][j],dp[i][j+1])-dungeon[i][j]);
地下城游戏
来源: http://www.bubuko.com/infodetail-3191928.html