LintCode (110) 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.

Have you met this question in a real interview? 

Yes

Example

Note

You can only move either down or right at any point in time.

求最小， 矩阵，-》 matrix dp。 

列方程：

f[i][j] = 从0,0 到 i,j的最小和。

转移方程 f[i][j] = min(f[i-1][j], f[i][j-1]) +grid[i][j]

初始条件， f[0][*], f[*][0]

解， f[m-1][n-1]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { public: /** * @param grid: a list of lists of integers. * @return: An integer, minimizes the sum of all numbers along its path */ int minPathSum(vector<vector<int> > &grid) { // write your code here int m = grid.size(); int n = grid[0].size(); // state f[i][j] is the minmum sum from [0][0] goes to here vector<vector<int> > tbl(m, vector<int>(n, 0)); tbl[0][0]=grid[0][0]; for (int i=1; i<m; i++){ tbl[i][0]=tbl[i-1][0]+grid[i][0]; } for (int i=1; i<n; i++){ tbl[0][i]= tbl[0][i-1]+grid[0][i]; } for (int i=1; i<m; i++){ for (int j=1; j<n; j++){ tbl[i][j]=min(tbl[i][j-1],tbl[i-1][j])+grid[i][j]; } } return tbl[m-1][n-1]; } };