3 条题解
-
6
这个问题可以使用动态规划来解决。我们定义一个二维数组dp,其中dp[i][j]表示从左上角到达网格中第i行第j列的位置的路径上的数字总和的最小值。
首先,我们可以初始化dp数组的第一行和第一列。对于第一行,dp[0][j] = dp[0][j-1] + grid[0][j],表示从左上角到达第一行每个位置的路径上的数字总和都是前一个位置的数字总和加上当前位置的数字。同理,对于第一列,dp[i][0] = dp[i-1][0] + grid[i][0]。
然后,我们可以计算其他位置的dp值。对于位置(i, j),可以选择从上方位置(i-1, j)或者从左边位置(i, j-1)移动而来,我们选择路径上数字总和更小的一条路径,即dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
最后,dp[n-1][m-1]就表示从左上角到右下角的路径上的数字总和的最小值。
这个问题的时间复杂度是O(nm),其中n和m分别是grid的行数和列数。空间复杂度也是O(nm),需要一个与grid相同大小的dp数组来保存中间结果。
该问题本质上是一个典型的求最优路径问题,通过使用动态规划的思想,我们可以有效地解决该问题。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int minimumPathSum(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]; } // 计算其他位置的dp值 for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]; } } return dp[n-1][m-1]; } int main() { int n, m; cin >> n >> m; vector<vector<int>> grid(n, vector<int>(m, 0)); // 读取输入 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> grid[i][j]; } } // 调用函数并输出结果 int result = minimumPathSum(grid); cout << result << endl; return 0; }
-
3
#include <iostream> using namespace std; int n, m, a[105][105], f[105][105]; int main(){ cin>>n>>m; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin>>a[i][j]; } } f[1][1]=a[1][1]; for(int i = 2;i <= n;i++){ f[i][1]=f[i-1][1]+a[i][1]; } for(int i = 2;i <= m;i++){ f[1][i]=f[1][i-1]+a[1][i]; } for(int i = 2;i <= n;i++){ for (int j = 2;j <= m;j++){ f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j]; } } cout<<f[n][m]; return 0; }
-
1
思路
由于路径的方向只能是向下或向右,因此网格的第一行的每个元素只能从左上角元素开始向右移动到达,网格的第一列的每个元素只能从左上角元素开始向下移动到达,此时的路径是唯一的,因此每个元素对应的最小路径和即为对应的路径上的数字总和。对于不在第一行和第一列的元素,可以从其上方相邻元素向下移动一步到达,或者从其左方相邻元素向右移动一步到达,元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值。由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关,因此可以使用动态规划求解。
创建二维数组 ,与原始网格的大小相同, 表示从左上角出发到 位置的最小路径和。显然,。对于 中的其余元素,通过以下状态转移方程计算元素值。
(1)当 且 时,。
(2)当 且 时,
(3)当 且 时,
最后得到 的值即为从网格左上角到网格右下角的最小路径和。
代码
</p>#include<iostream> using namespace std; int grid[105][105], f[105][105]; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> grid[i][j]; } } f[1][1] = grid[1][1]; for (int i = 2; i <= n; i++) { f[i][1] = f[i - 1][1] + grid[i][1]; } for (int j = 2; j <= m; j++) { f[1][j] = f[1][j - 1] + grid[1][j]; } for (int i = 2; i <= n; i++) { for (int j = 2; j <= m; j++) { f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]; } } cout << f[n][m];
}
- 1
信息
- ID
- 353
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 369
- 已通过
- 290
- 上传者