一、题目二、做题思路2.1 状态表示核心基础本题要求计算从左上角到右下角的路径上数字总和的最小值。由于网格是二维的我们定义dp[i][j]表示从起点(0,0)到达网格第i-1行第j-1列位置时的最小累计路径和。2.2 状态转移方程关键难点每次只能向右或向下移动一步因此到达当前格子的最后一步要么来自上方(i-1, j)要么来自左方(i, j-1)。为了获得最小和我们选择两者中累计路径和较小的那个再加上当前格子的数值grid[i-1][j-1]dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i-1][j-1]。2.3 初始化边界防护由于多开了一行一列且我们希望递推公式对所有格子包括起点统一生效需要特殊处理虚拟边界将dp数组所有元素初始化为INT_MAX表示不可达。设置dp[0][1] dp[1][0] 0作为虚拟起点的“入口”使得计算 起点(1,1)时min(dp[0][1], dp[1][0]) 0从而正确得到dp[1][1] grid[0][0]。2.4 填表顺序递推方向计算dp[i][j]依赖dp[i-1][j]上方和dp[i][j-1]左方这些位置的行号或列号均小于当前值。因此必须从上到下、从左到右即先行后列双重循环递增依次填充dp表确保每个状态计算时其所有前置状态均已就绪。2.5 返回值目标映射题目要求返回从起点到达右下角的最小路径和。右下角在原网格中的坐标为(m-1, n-1)对应dp表中的dp[m][n]因为多开了一行一列。因此直接返回dp[m][n]该值即为所求。三、代码class Solution { public: int minPathSum(vectorvectorint grid) { // 1. 创建dp表 int row grid.size(); int col grid[0].size(); // 多开一行一列dp[row1][col1]作为虚拟边界便于统一处理边界情况 // 所有位置初始化为 INT_MAX使得只有有效路径才会被更新 vectorvectorint dp(row 1, vectorint(col 1, INT_MAX)); // 2. 初始化 // 技巧将虚拟起点设在 (0,1) 和 (1,0)使它们为 0 // 这样在计算 dp[1][1]真正的起点时min(dp[0][1], dp[1][0]) 0 // 加上 grid[0][0] 后得到正确的起点路径和。 // 这种写法避免了单独处理起点的繁琐让递推公式对所有格子统一生效。 dp[0][1] dp[1][0] 0; // 3. 填表顺序从上到下从左到右 // 因为 dp[i][j] 依赖于 dp[i-1][j]上方和 dp[i][j-1]左方 // 按行遍历即可保证依赖的子问题已经计算完毕。 for (int i 1; i row; i) { for (int j 1; j col; j) { // 4. 状态转移方程 // 到达当前格子的最小路径和 从上方或左方来的较小路径和 当前格子的权值 dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i - 1][j - 1]; } } // 5. 返回值dp[row][col] 即为从起点 (0,0) 到终点 (row-1, col-1) 的最小路径和 return dp[row][col]; } };四、流程图五、题目六、做题思路2.1 状态表示核心基础本题要求计算从起点出发到达终点所需的最低初始健康点数。由于路径决策依赖未来后续房间的消耗/增益我们采用从终点向起点逆推的方式。定义dp[i][j]表示从位置(i, j)出发到达右下角终点所需的最小初始生命值即进入(i, j)前至少需要多少血量。2.2 状态转移方程关键难点骑士每次只能向右或向下移动一步因此从(i, j)出发的下一步要么去右方(i, j1)要么去下方(i1, j)。为了确保后续路径存活进入(i, j)前的血量必须满足扣除当前房间的数值后仍能支撑下一步所需的最小血量。因此先计算min(dp[i][j1], dp[i1][j])选择右、下中所需血量较小的方向再减去当前房间的消耗/增益dungeon[i][j]得到进入该房间前所需的理论最低血量最后保证至少为 1血量不能为 0 或负dp[i][j] max(1, min(dp[i][j1], dp[i1][j]) - dungeon[i][j])。2.3 初始化边界防护为避免在右下角边界外访问采用多开一行一列dp尺寸为(m1)×(n1)所有元素初始化为INT_MAX表示不可达。关键技巧将终点的右方和下方虚拟格子设为1即dp[m][n-1] dp[m-1][n] 1。这表示从终点(m-1, n-1)到达终点即停留在终点所需的最小生命值为 1使得计算终点时min(1, 1) - dungeon[m-1][n-1]能正确推导出进入终点前所需血量。2.4 填表顺序递推方向计算dp[i][j]依赖dp[i][j1]右方和dp[i1][j]下方这些位置的行号或列号均大于当前值。因此必须从右下角向左上角即i从m-1到0j从n-1到0依次填充dp表确保每个状态计算时其所有后续状态均已就绪。2.5 返回值目标映射题目要求返回从起点(0,0)出发拯救公主所需的最低初始健康点数dp[0][0]正好表示该值。因七、代码class Solution { public: int calculateMinimumHP(vectorvectorint dungeon) { int row dungeon.size(); int col dungeon[0].size(); // 1. 创建dp表 // dp[i][j] 表示从位置 (i, j) 到达右下角 (row-1, col-1) 所需的最小初始生命值 // 多开一行一列dp[row1][col1]作为虚拟边界便于处理右下角边界 // 所有位置初始化为 INT_MAX只有有效路径才会被更新 vectorvectorint dp(row 1, vectorint(col 1, INT_MAX)); // 2. 初始化 // 技巧将终点右方和下方的虚拟格子设为 1 // 表示从终点 (row-1, col-1) 走到终点即停留在终点所需的最小生命值为 1。 // 这样在计算 dp[row-1][col-1] 时min(dp[row-1][col], dp[row][col-1]) 1 // 从而正确得到从终点出发至少需要 1 点血。 dp[row][col - 1] dp[row - 1][col] 1; // 3. 填表顺序从右下角向左上角遍历逆序 // 因为 dp[i][j] 依赖于 dp[i][j1]右方和 dp[i1][j]下方 // 所以从最后一行/列开始逆序遍历即可保证依赖的子问题已计算。 for (int i row - 1; i 0; i--) { for (int j col - 1; j 0; j--) { // 4. 状态转移方程 // 进入当前格子前所需的最小血量 // max(1, min(从右方进入所需血量, 从下方进入所需血量) - 当前格子的消耗/收益) // 其中 min(...) - dungeon[i][j] 表示进入当前格子并扣除/增加血量后仍能满足后续需求 // 再与 1 取 max 保证进入时血量至少为 1生命值不能为 0 或负数 int need min(dp[i][j 1], dp[i 1][j]) - dungeon[i][j]; dp[i][j] max(1, need); } } // 5. 返回值dp[0][0] 即为从起点 (0,0) 到达右下角所需的最小初始生命值 return dp[0][0]; } };八、流程图