注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex64 Minimum Path Sum  

2015-05-18 21:57:40|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
ex62和ex63的升级版,这次直接把所有的最小路径求出来了,原本也是打算用递归的,想了想还是用滚动算法吧!

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.

这一题和有一题,遍历三角形那个很像,都是要去除冗余项。

/*
* 和 ex62 ex63 基本上一样的
* 其实也可以用递归来做,但是,看着题的架势估计又会说超时了
*/
int minPathSum(int** grid, int gridRowSize, int gridColSize) {
int m = gridRowSize;
int n = gridColSize;
int i, j;
int **matrix = (int**)malloc(m*sizeof(int*));
for (i = 0; i < m; i++)
{
matrix[i] = (int*)malloc(n*sizeof(int));
for (j = 0; j < n; j++)
matrix[i][j] = 0;
}
matrix[0][0] = grid[0][0];
for (i = 1; i < m; i++)
{
matrix[i][0] = grid[i][0] + matrix[i - 1][0]; //第一列赋值
//printf("%d ",matrix[i][0]);
}
//printf("\n");
for (i = 1; i < n; i++)
{
matrix[0][i] = grid[0][i] + matrix[0][i - 1]; //第一行赋值
//printf("%d ", matrix[0][i]);
}
//printf("\n");

int min;
for (i = 1; i < m; i++)
{
for (j = 1; j < n; j++)
{
min = matrix[i - 1][j] < matrix[i][j - 1] ? matrix[i - 1][j] : matrix[i][j - 1];
matrix[i][j] = grid[i][j]+ min;
}
}
int result = matrix[m - 1][n - 1];
for (i = 0; i < m; i++)
free(matrix[i]);
free(matrix);

return result;
}






  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018