# leetcode 64. Minimum Path Sum (二维dp)

Posted by 111qqz on Monday, April 10, 2017

## TOC

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.

wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。

``````/* ***********************************************
Author :111qqz
Created Time :2017年04月10日 星期一 10时11分26秒
File Name :64.cpp
************************************************ */
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
vector<vector<int> > dp(n+1,vector<int>(m+1,0x3f3f3f3f)); //求最小路径，初始化为最大值。

dp[n-1][m-1] = grid[n-1][m-1];
for ( int i = n-1 ;  i >= 0 ; i--)
{
for ( int j = m-1 ; j >= 0 ; j--)
{
if (i==n-1&&j==m-1) continue;
dp[i][j] = min(dp[i+1][j],dp[i][j+1]) + grid[i][j];
}
}

for ( int i = 0 ; i < n ; i++)
{
for ( int j = 0 ; j < m ; j++)
printf("%d ",dp[i][j]);
printf("\n");
}
int res = dp[0][0];
cout<<"res:"<<res<<endl;
return res;
}
};
``````

「真诚赞赏，手留余香」