题目来源
https://leetcode.com/problems/minimum-path-sum/
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
题意分析
Input:a matrix with weight
Output:the minimum sum of the path from top-left to down-right
Conditions:经过路径和最小，只能向右或向下
题目思路
和上题一样采用动态规划，动态方程几乎没变，dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
初始化第一行和第一列直接用grid和前一个位置的值即可
AC代码（Python）
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
n = len(grid[0]) dp = [[i for i in range(n)] for j in range(m)] dp[0][0] = grid[0][0] for i in range(1, n):
dp[0][i] = dp[0][i - 1] + grid[0][i] for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0] for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] return dp[m - 1][n - 1]
