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

简答题

编程实现:

路径最小和

题目描述:

有一个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 or not matrix[0]:return 0n, m = len(matrix), len(matrix[0])dp = [[0] * (m + 1) for _ in range(n + 1)]dp[0][1:] = [row[0] for row in matrix]for i in range(1, n + 1):dp[i][0] = dp[i - 1][0] + matrix[i - 1][0]for i in range(1, n + 1):for j in range(1, m + 1):dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i - 1][j - 1]return dp[n][m]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`数组的值。

我们可以发现,从左上角方格到任意位置`(i, j)`方格的最小路径和,可以通过从上方方格`(i-1, j)`和左方方格`(i, j-1)`移动到位置`(i, j)`方格的最小路径和中的较小值,加上位置`(i, j)`方格的值得到。

因此,我们可以使用动态规划算法,从左上角方格开始,逐步更新`dp`数组的值,直到更新到右下角方格。最后,`dp[n][m]`即为最小路径和。

在代码中,我们首先将`dp`数组的第一行和第一列初始化,然后逐步更新`dp`数组的值,最后输出`dp[n][m]`即可。
创作类型:
原创

本文链接:编程实现: 路径最小和 题目描述: 有一个N*M的矩阵方格,每个方格中都有一个正整数,现从左上角方格

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

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

分享考题
share