美文网首页
64 minimum path sum

64 minimum path sum

作者: larrymusk | 来源:发表于2017-12-05 11:09 被阅读0次
/*
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];
}

相关文章

网友评论

      本文标题:64 minimum path sum

      本文链接:https://www.haomeiwen.com/subject/rsvqixtx.html