064._minimum_path_sum.md

###64. Minimum Path Sum

题目: https://leetcode.com/problems/minimum-path-sum/

难度:

Medium

非常明显的DP

状态转移方程

dp[i][j] = gird[i][j] + min(dp[i-1][j], dp[i][j-1])

然后注意一下边界的处理，一开始dp[0][0] = grid[0][0]

第一行和第一列，之后开始全用状态转移方程

class Solution(object):
	def minPathSum(self, grid):
		"""
		:type grid: List[List[int]]
		:rtype: int
		"""
		m = len(grid)
		n = len(grid[0]) if m else 0

		dp = [[0 for i in range(n)] for i in range(m)]

		dp[0][0] = grid[0][0]

		# first row
		for i in range(1,n):
			dp[0][i] = grid[0][i] + dp[0][i-1]

		# first col
		for i in range(1,m):
			dp[i][0] = grid[i][0] + dp[i-1][0]


		for i in range(1,m):
			for j in range(1,n):
				dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

		
		return dp[m-1][n-1]