【题目描述】
Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.
给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
【注】：你在同一时间只能向下或者向右移动一步
【题目链接】
www.lintcode.com/en/problem/minimum-path-sum/
【题目解析】
本题是动态规划基本的基本类型。该题的思想是建立f[i][j]，表示从起点到f[i][j]最小权值。
由于(i,j)只能由(i-1,j)和(i,j-1)两个点到达，假设我们已经知道了f[i-1][j]和f[i][j-1]，则f[i][j]的最小值等于min(f[i-1][j], f[i][j - 1])加上当前(i,j)的权值，即：
f[i][j] = g[i][j] + min(f[i - 1][j], f[i][j - 1])
所以我们通过行列的递推，就能够得到从左上角到右下角的最小权值f[m][n]，时间复杂度为O(mn)。
【参考答案】
