[leetcode] Minimum Path Sum

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.

分析：动态规划：

状态转移公式为：ret[i][j] = min(ret[i-1][j], ret[i][j-1]) + grid[i][j];

对于矩阵

1	2	3
4	5	6
7	8	9

它所对应的ret矩阵为：

1	1+2	1+2+3
1+4	1+2+5	1+2+3+6
1+4+7	1+2+5+8	1+2+3+6+9

1	3	6
5	8	12
12	16	21

代码如下：

 1 class Solution
 2 {
 3 public:
 4   int minPathSum(vector<vector<int> > &grid)
 5   {
 6     if(grid.size() == 0)
 7       return 0;
 8 
 9     vector<vector<int> > ret(grid);
10 
11     for(int i=1; i<grid.size(); i++)
12       ret[i][0] += ret[i-1][0];
13 
14     for(int j=1; j<grid[0].size(); j++)
15       ret[0][j] += ret[0][j-1];
16 
17     for(int i=1; i<grid.size(); i++)
18       for(int j=1; j<grid[i].size(); j++)
19         ret[i][j] = min(ret[i][j-1], ret[i-1][j]) + grid[i][j];
20 
21     return ret[grid.size()-1][grid[0].size()-1];
22   }
23 };