算法---动态规划练习-6（地下城游戏）

本文主要是介绍算法---动态规划练习-6（地下城游戏），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目解析

题目地址：点这里

2. 讲解算法原理

---

1. 首先，定义一个二维数组 dp，其中 dp[i][j] 表示从位置 (i, j) 开始到达终点时的最低健康点数。

2. 初始化数组 dp 的边界条件：

• 对于最后一行，即 dp[m-1][j]（其中 m 是行数），表示最后一行的每个位置到达终点时的最低健康点数。由于只能向右移动，所以从最后一行的任意位置出发都必须向右移动到达终点，因此初始化为 1。
• 对于最后一列，即 dp[i][n-1]（其中 n 是列数），表示最后一列的每个位置到达终点时的最低健康点数。由于只能向下移动，所以从最后一列的任意位置出发都必须向下移动到达终点，因此初始化为 1。

3. 初始化除了最后一行和最后一列之外的其他位置 dp[i][j] 的值为正无穷大（INT_MAX），表示无法到达终点。

4. 从倒数第二行开始，从右往左，从下往上遍历整个地牢。对于每个位置 (i, j)，计算到达终点的最低健康点数：

• 使用状态转移方程 dp[i][j] = min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j]，表示选择向右移动和向下移动中所需最低健康点数较小的那个，并减去当前位置的健康点数消耗。
• 对于 dp[i][j] 的值，还需要确保其不会小于 1，因为健康点数不能为负数。

5. 最后，返回 dp[0][0]，即起点位置的最低健康点数。

---

3. 编写代码

class Solution {
public://状态表示：以i位置为起点，到达终点时的最低健康点数（此题以i位置为结尾解不出来！！！）int calculateMinimumHP(vector<vector<int>>& dungeon) {int m=dungeon.size();int n=dungeon[0].size();vector<vector<int>> dp(m+1,vector<int>(n+1));dp[m-1][n]=1,dp[m][n-1]=1;for(int i=0;i<n-1;i++) dp[m][i]=INT_MAX;for(int j=0;j<m-1;j++) dp[j][n]=INT_MAX;for(int i=m-1;i>=0;i--){for(int j=n-1;j>=0;j--){//状态转移方程！！！！dp[i][j]=min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];dp[i][j]=max(1,dp[i][j]);}}return dp[0][0];}
};

这篇关于算法---动态规划练习-6（地下城游戏）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---