美文网首页
每周一道算法题(四十八)

每周一道算法题(四十八)

作者: CrazySteven | 来源:发表于2018-04-01 20:14 被阅读18次

    本周题目难度'Medium',使用语言'C'

    我的小多肉镇楼

    题目:给你一个gridRowSize*gridColSize的格子,格子里有数字,从左上角走到右下角(和上周的题一样只能往右走或往下走),求所经过数字之和最小的数字

    思路:这又是一道动态规划(Dynamic Programming,俗称DP)的题,思路很简单,和上周的第一道题基本上一样,就是把左边或者上边较小的值加上当前格子里的值(上周是左边的值加上上边的值)然后就OK了,看代码:

    int minPathSum(int** grid, int gridRowSize, int gridColSize) {
        //定义一个数组
        int res[gridColSize];
        //原点的值
        res[0] = grid[0][0];
        //先写出第一行(当前格子的值加上左边的值)
        for (int i = 1;i < gridColSize; i++) res[i] = grid[0][i] + res[i-1];
        for (int i = 1;i < gridRowSize; i++)    
            for (int j = 0;j < gridColSize; j++)  
            //如果是第一列则是上边的值加当前格子的值,否则就是左边与上边较小的值加上当前格子的值
                res[j] = (j ? (res[j] < res[j-1] ? res[j] : res[j-1]) : res[j])+ grid[i][j];
        return res[gridColSize-1]; 
    }
    

    效率666,动规的题解释起来很麻烦,我学了两周也没能很好的掌握,网上虽然有很多信息,但都比较雷同,还有就是做题太慢了,去面试的时候做一道算法题都是在十分钟之内,我一般都要做好几天。。。

    版权声明:本文为 Crazy Steven 原创出品,欢迎转载,转载时请注明出处!

    相关文章

      网友评论

          本文标题:每周一道算法题(四十八)

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