A25720. 编程实现：有一个N*M的矩阵方格，每个方格中都有一个正整数，现从左上角方格出发向右下角方格移动，每次只能向下或向右移动一个方格，请你找出一条最小路径，并输出该路径上的正整数之和。最小路径：这条路径上的正整数之和最小。例如：N=2，M=3，2*3的矩阵方格中的正整数如下，按照移动规则，从左上角方格移动到右下角方格的路径共3条，分别为1->3->5->6，1->3->4->6，1->2->4->6，…
填空题
中等
知识点
题目描述
编程实现：
有一个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参考答案
def min_path_sum(m):
if m == None or len(m) == 0 or m[0] == None or len(m[0]) == 0:
return 0
row = len(m)
col = len(m[0])
dp = [[0]*col for i in range(row)]
dp[0][0] = m[0][0]
for i in range(0, row):
dp[i][0] = dp[i-1][0] + m[i][0]
for j in range(0, col):
dp[0][j] = dp[0][j-1] + m[0][j]
for i in range(1, row):
for j in range(1, col):
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + m[i][j]
return dp[row-1][col-1]
matrix=[]
s=input()
list_t=s.split(',')
n=int(list_t[0])
m=int(list_t[1])
for i in range(n):
v=input()
list_temp=v.split(',')
for i in range(len(list_temp)):
list_temp[i]=int(list_temp[i])
matrix.append(list_temp)
res = min_path_sum(matrix)
print(res)答案解析
评分标准：
7分：能正确输出一组数据；
7分：能正确输出两组数据；
7分：能正确输出三组数据；
7分：能正确输出四组数据；
7分：能正确输出五组数据。
上一题
下一题