01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 #include <set>
05 #include <string>
06 using namespace std;
07
08 const int inf = 0x3f3f3f3f;
09
10 int calc(vector<vector<int>> &grid)
11 {
12    int m = grid.size(), n = grid[0].size();
13    vector<vector<int>> dp(m + 1, vector<int>(n + 1, inf));
14    dp[0][0] = grid[0][0];
15    for(int i = 0; i < m; i++)
16        for(int j = 0; j < n; j++)
17        {
18            if(i > 0)
19                dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j]);
20            if(j > 0)
21                dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j]);
22        }
23    return dp[m - 1][n - 1];
24 }
25
26 int main()
27 {
28    int m, n;
29    cin >> m >> n;
30    vector<vector<int>> a(m, vector<int>(n));
31    for(int i = 0; i < m; i++)
32        for(int j = 0; j < n; j++)
33            cin >> a[i][j];
34    cout << calc(a) << endl;
35    return 0;
36 }

条件：假设 ( $m <=100$ )，( $n <=10000$ )。

第 1 题

若输入 2 3 1 2 3 4 5 6，则输出为 10。
{{ select(1) }}

• 正确
• 错误

第 2 题

计算 dp 数组的时间复杂度为 ( O(n^2) )。
{{ select(2) }}

• 正确
• 错误

第 3 题

（2分）在 calc 函数中，访问 dp[m][n] 不会发生越界错误。
{{ select(3) }}

• 正确
• 错误

第 4 题

当输入的 a 数组为
({1, 3, 1}, {1, 5, 1}, {4, 2, 1}) 时，程序输出为（ ）
{{ select(4) }}

• 4
• 7
• 6
• 5

第 5 题

若将第 19 行改为
dp[i][j] = min(dp[i][j], dp[i-1][j] - grid[i][j])，
则当输入的 a 数组为 ({1, 2, 3}, {4, 5, 6}) 时，程序的输出为（ ）
{{ select(5) }}

• -3
• -2
• -1
• 0

第 6 题

（4分）若将第 10 行中的 & 符号去除，可能出现什么情况？（ ）
{{ select(6) }}

• dp 数组计算错误
• calc 函数中的 grid 数组和 a 数组不一致
• 无影响
• 发生编译错误