/*
d[0][0] = grid[0][0]
d[i][j] = min(d[i][j-1], d[i-1][j])+grid[i][j]
d[i][0] = d[i-1][0]+grid[i][0]
d[0][j] = d[0][j-1]+grid[0][j];
*/
#define min(a,b) (a>b?b:a)
int minPathSum(int** grid, int gridRowSize, int gridColSize) {
int (*dp)[gridColSize] = calloc(gridRowSize*gridColSize,sizeof(int));
int i,j;
dp[0][0] = grid[0][0];
for(i = 1; i < gridRowSize; i++)
dp[i][0] = dp[i-1][0] + grid[i][0];
for(j = 1; j < gridColSize; j++)
dp[0][j]= dp[0][j-1] + grid[0][j];
for(i = 1; i < gridRowSize; i++)
for(j = 1; j < gridColSize; j++)
dp[i][j] = min(dp[i][j-1], dp[i-1][j])+grid[i][j];
return dp[gridRowSize-1][gridColSize-1];
}
网友评论