二维数组 h、v 分别表示网格中「水平边」「垂直边」的时间消耗。程序用动态规划计算从左下角 dis[0][0] 到右上角 dis[y][x] 的最小时间消耗。横线处应填写哪个选项？
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]);
正确答案：C