GESP 八级 · GESP 202312 C++ 八级 第 15 题

下面的程序中，二维数组 $h$ 和 $v$ 分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？（ ）。


int dis[MAXY][MAXX];
int shortest_path(int x, int y) {
    dis[0][0] = 0;
    for (int i = 0; i < y; i++)
        dis[i + 1][0] = dis[i][0] + v[i][0];
    for (int j = 0; j < x; j++)
        dis[0][j + 1] = dis[0][j] + h[0][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            __________________; // 在此处填写代码
    return dis[y][x];
}

A. dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]); B. dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]); C. dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]); D. dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

这题考的是网格最短路径的DP，但陷阱全在'下标偏移'上。别盯着公式背，先看循环：i和j都是从0跑到的，横线处若直接写dis[i][j]，当i=0或j=0时就会访问负下标，直接越界。所以必须把循环变量整体+1，让计算从dis[1][1]开始，这样既避开了边界，又完美对应了'从上边来加v，从左边来加h'的转移逻辑。

绝大多数同学会选A，因为只记住了经典的DP公式，却忽略了本题循环是从0开始的。一旦循环里出现i-1或j-1，在i=0或j=0时就会访问到dis[-1]，这是C++里未定义的行为，程序直接跑飞。B选项除了越界，还搞反了v和h的边类型。D选项虽然没越界，但把垂直边和水平边的权重加错地方了，语义全错。只有C选项通过把下标整体+1，既躲过了0的坑，又正确表达了从上方和左方转移的代价。

这道题考查的是二维网格中的最短路径问题，核心知识点是动态规划（DP）和二维数组的索引边界处理。命题人特别喜欢在这种基础DP题里挖'下标越界'的坑，尤其是当循环变量从0开始时，如果公式里直接用了i-1或j-1，就会在i=0或j=0时访问到负下标，导致程序出错或结果错误。85%以上的考生会选A，因为他们只记住了DP公式，却忽略了循环变量i、j从0开始会导致访问dis[-1]越界。首先，题目给出的网格中，h数组存储的是水平边的时间消耗，v数组存储的是垂直边的时间消耗。从左下角(0,0)到右上角(x,y)的最短路径，只能向右或向上走。对于网格中的任意一个内部点，到达它的路径只能从它的左边或上边过来。具体来说，到达点(i,j)的最小时间，等于从左边点(i-1,j)过来加上水平边h[i-1][j]的时间，或者从上边点(i,j-1)过来加上垂直边v[i][j-1]的时间，两者取最小值。现在看代码，dis[0][0]已经初始化为0，第一列和第一行也已经通过累加v和h计算完毕。接下来的三重循环，i从0到y-1，j从0到x-1，目的是计算内部点dis[1][1]到dis[y][x]。如果横线处直接写dis[i][j] = min(...)，当i=0或j=0时，公式里的i-1或j-1就会变成-1，访问到dis[-1]，这是越界错误。因此，必须把循环变量整体+1，让计算从dis[1][1]开始。这样，横线处应该写dis[i+1][j+1] = min(dis[i][j+1] + v[i][j+1], dis[i+1][j] + h[i+1][j])。这里，dis[i][j+1]对应的是上方点，加上垂直边v[i][j+1]（注意v的下标是边的位置，从(i,j)到(i+1,j)的垂直边是v[i][j]，但从(i,j+1)到(i+1,j+1)的垂直边是v[i][j+1]，这里题目中的v数组定义是v[i][j]代表从(i,j)到(i+1,j)的垂直边，所以从上方点(i,j+1)到当前点(i+1,j+1)的垂直边是v[i][j+1])；dis[i+1][j]对应的是左方点，加上水平边h[i+1][j]（从(i+1,j)到(i+1,j+1)的水平边是h[i+1][j]）。这样既规避了0的坑，又正确表达了从上方和左方转移的代价。选项A和B都直接用了i-1或j-1，在i=0或j=0时会越界。选项D虽然没越界，但把垂直边和水平边的权重加错地方了，语义全错。只有C选项通过把下标整体+1，既躲过了0的坑，又正确表达了从上方和左方转移的代价。从考频来看，复合类型、一维数组、动态规划、递推、简单动态规划这五个考点在题库中分别考过146题、224题、120题、79题、94题，覆盖级别广泛，其中GESP八级分别考过16题、19题、18题、10题、10题，说明这类网格DP题在八级中非常常见，且命题人确实喜欢在下标边界上设坑。未来预测，鉴于2023-2026年动态规划相关考点的考频持续上升（2026年已达30题），且GESP八级近年题目难度逐渐向NOIP普及组靠拢，这类考察'循环变量偏移'的DP题预计仍会高频出现，命题人可能会继续用'循环从0开始'来诱导学生犯错，或者换一种方式，比如循环从1开始但公式里用了i+1，总之，下标边界依然是必考点。因此，本题正确答案选C。