刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

编程实现：

有一个N*M的矩阵方格，每个方格中都有一个正整数，现从左上角方格出发向右下角方格移动，每次只能向下或向右移动一个方格，请你找出一条最小路径，并输出该路径上的正整数之和。

最小路径：这条路径上的正整数之和最小。

例如：N=2，M=3，2*3的矩阵方格中的正整数如下，

按照移动规则，从左上角方格移动到右下角方格的路径共3条，分别为1->3->5->6，1->3->4->6，1->2->4->6，3条路径上的正整数之和分别为15、14和13，其中正整数之和最小的一条路径是1->2->4->6，和为13，故输出13。

输入描述：

第一行输入两个正整数N和M（2≤N≤100，2≤M≤100），N表示矩阵方格的行数，M表示矩阵方格的列数，两个正整数之间以一个英文逗号隔开

第二行开始输入N行，每行M个正整数（1≤正整数≤200），正整数之间以一个英文逗号隔开

输出描述：

输出一个整数，表示最小路径上的正整数之和


样例输入：

2,3
1,3,5
2,4,6

样例输出：

13

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```pythondef min_path_sum(matrix):if not matrix:return 0rows, cols = len(matrix), len(matrix[0])dp = [[0] * cols for _ in range(rows)]dp[0][0] = matrix[0][0]for i in range(1, rows):dp[i][0] = dp[i-1][0] + matrix[i][0]for j in range(1, cols):dp[0][j] = dp[0][j-1] + matrix[0][j]for i in range(1, rows):for j in range(1, cols):dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]return dp[-1][-1]N, M = map(int, input().split(','))matrix = [list(map(int, input().split(','))) for _ in range(N)]print(min_path_sum(matrix))```

解析：

【喵呜刷题小喵解析】：

这个问题可以使用动态规划来解决。首先，我们定义一个二维数组dp，其中dp[i][j]表示从左上角到(i, j)位置的最小路径和。

对于dp[0][0]，它只包含一个元素，即matrix[0][0]，所以dp[0][0] = matrix[0][0]。

对于dp[0][j]，其中j > 0，它表示从左上角到第一行的第j个方格的最小路径和。由于只能向下移动，所以dp[0][j] = dp[0][j-1] + matrix[0][j]。

对于dp[i][0]，其中i > 0，它表示从左上角到第i行的第一个方格的最小路径和。由于只能向右移动，所以dp[i][0] = dp[i-1][0] + matrix[i][0]。

对于dp[i][j]，其中i > 0且j > 0，它表示从左上角到(i, j)位置的最小路径和。由于只能向下或向右移动，所以dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]。

最后，返回dp[-1][-1]，即从左上角到右下角的最小路径和。

在代码中，我们首先定义了一个函数min_path_sum，它接受一个二维数组matrix作为输入，并返回最小路径和。然后，我们读取输入，将输入的矩阵存储在matrix中，并调用min_path_sum函数来计算最小路径和，最后输出结果。
创作类型：
原创

本文链接：编程实现： 有一个N*M的矩阵方格，每个方格中都有一个正整数，现从左上角方格出发向右下角方格移动，每

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share