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

HT·生活

123

 
 
 

日志

 
 

ex62 Unique Paths  

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

  下载LOFTER 我的照片书  |
求解到达指定点的路径的条数

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

ex62 Unique Paths - HT - HT·生活

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.


呵呵,我直接写了一个combination的函数,见c代码

long long int combination(int m, int n)
{
int i, j;
int num = m;
long long int result = 1;
int index = 1;
for (i = 0; i < n; i++)
{
result = result*num/index;
index++;
num = num - 1;
}
return result;
}
int uniquePaths1(int m, int n) {
if (m <= 1)
{
return 1;
}
if (n <= 1)
{
return 1;
}
int totalStep = m + n - 2;
int down = n - 1;

if (down > totalStep / 2)
{
down = totalStep - down;
}

long long int result = combination(totalStep,down);
return result;
}

后来意识到应该用递推的算法,见c代码

int uniquePaths(int m, int n) {
//网上看到一个方法,用滚动数组的方法求解
int i, j;
int **matrix = (int**)malloc(m*sizeof(int*));
for (i = 0; i < m; i++)
{
matrix[i] = (int*)malloc(n*sizeof(int));
}
for (i = 0; i < m; i++)
matrix[i][0] = 1; //第一列赋值为1
for (i = 0; i < n; i++)
matrix[0][i] = 1; //第一行赋值为1

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

return result;
}


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

历史上的今天

评论

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

页脚

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