问题描述
有一个矩阵map，它每个格子有一个权值。从左上角的格子开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。
问题分析
假设，一个矩阵map的行数n和列数m，且矩阵中从左上角出发到达第i行，第j列的最小路径为f(i,j)，则：
对于i=0, j=0, 很显然，f(0,0) = map[0][0]
对于第一行元素，即
来说，最小路径为从矩阵左上角出发到达前一位置（第0行，第j-1列）的最小路径 + 当前位置的权值。即,
同理，对于第一列元素，即
来说，最小路径为从矩阵左上角出发到达前一位置（第0列，第i-1行）的最小路径 + 当前位置的权值。即,
对于其他元素，即
来说，最小路径为从矩阵左上角出发到达前2个位置(i-1, j)以及(i, j-1)中的较小值 + 当前位置的权值。即
我们要求的是
代码实现
class Solution:
def MinsumPath(self,matrix,n,m):
dp= [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = matrix[0][0]
for i in range(1,n):
dp[i][0] = dp[i-1][0] + matrix[i][0]
for i in range(1,m):
dp[0][i] = dp[0][i-1] + matrix[0][i]
for i in range(1,n):
for j in range(1,m):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
return dp[n-1][m-1]
京公网安备 11010502036488号