Leetcode 64. 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.

分析

给出一个非负整数的矩阵，找出从左上角到右下角数值之和最小的路径。
也是使用动态规划的思想，看从→和↓两个方向到达的路径哪条上的数值之和更小。
最后输出值即可。类似的：http://www.jianshu.com/p/717ccf2d69ee

int minPathSum(int** grid, int gridRowSize, int gridColSize) {
    int * ans=(int *)malloc(sizeof(int)*gridColSize);
    ans[0]=grid[0][0];
    for(int i=1;i<gridColSize;i++)
    {
        ans[i]=grid[0][i]+ans[i-1];
    }
    for(int i=1;i<gridRowSize;i++)
    {
        ans[0]=ans[0]+grid[i][0];
        for(int j=1;j<gridColSize;j++)
        {
            if(ans[j]<ans[j-1])
                ans[j]=ans[j]+grid[i][j];
            else
                ans[j]=ans[j-1]+grid[i][j];
        }
    }
    return ans[gridColSize-1];
}

版权声明：本文来源简书，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://www.jianshu.com/p/34b1ea7ec8dc
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-01-08 21:41:48
阅读 ( 1316 )
分类：算法

Leetcode 64. Minimum Path Sum

题目

分析

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看