企业官网建设流程全解析

一、题目

二、做题思路

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(vector<vector<int>>& grid) { // 1. 创建dp表 int row = grid.size(); int col = grid[0].size(); // 多开一行一列（dp[row+1][col+1]）作为虚拟边界，便于统一处理边界情况 // 所有位置初始化为 INT_MAX，使得只有有效路径才会被更新 vector<vector<int>> dp(row + 1, vector<int>(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, j+1)，要么去下方(i+1, j)。为了确保后续路径存活，进入(i, j)前的血量必须满足：扣除当前房间的数值后，仍能支撑下一步所需的最小血量。因此，先计算min(dp[i][j+1], dp[i+1][j])（选择右、下中所需血量较小的方向），再减去当前房间的消耗/增益dungeon[i][j]，得到进入该房间前所需的理论最低血量，最后保证至少为 1（血量不能为 0 或负）：
dp[i][j] = max(1, min(dp[i][j+1], dp[i+1][j]) - dungeon[i][j])。

2.3 初始化（边界防护）

为避免在右下角边界外访问，采用多开一行一列（dp尺寸为(m+1)×(n+1)），所有元素初始化为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][j+1]（右方）和dp[i+1][j]（下方），这些位置的行号或列号均大于当前值。因此必须从右下角向左上角（即i从m-1到0，j从n-1到0）依次填充dp表，确保每个状态计算时，其所有后续状态均已就绪。

2.5 返回值（目标映射）

题目要求返回从起点(0,0)出发拯救公主所需的最低初始健康点数，dp[0][0]正好表示该值。因

七、代码

class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int row = dungeon.size(); int col = dungeon[0].size(); // 1. 创建dp表 // dp[i][j] 表示从位置 (i, j) 到达右下角 (row-1, col-1) 所需的最小初始生命值 // 多开一行一列（dp[row+1][col+1]）作为虚拟边界，便于处理右下角边界 // 所有位置初始化为 INT_MAX，只有有效路径才会被更新 vector<vector<int>> dp(row + 1, vector<int>(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][j+1]（右方）和 dp[i+1][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]; } };

八、流程图