丝路新程的地下管廊铺设光缆,不同路段的铺设成本不同。给定一个 n×m 的网格,每个格子代表一段管廊的成本,机器人从左上角出发,只能向右或向下移动,目标是到达右下角。以下代码使用动态规划计算最小成本,请问横线处应填入的代码是:
int minCost(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int>> dp(n, vector<int>(m, 0));
dp[0][0] = grid[0][0];
for(int i = 1; i < n; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for(int j = 1; j < m; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
dp[i][j] = grid[i][j] + _______________;
}
}
return dp[n-1][m-1];
15 }
min(dp[i-1][j], dp[i][j-1])
max(dp[i-1][j], dp[i][j-1])
dp[i-1][j] + dp[i][j-1]
min(dp[i-1][j-1], dp[i][j])