我的小多肉镇楼本周题目难度'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,动规的题解释起来很麻烦,我学了两周也没能很好的掌握,网上虽然有很多信息,但都比较雷同,还有就是做题太慢了,去面试的时候做一道算法题都是在十分钟之内,我一般都要做好几天。。。
网友评论