首页 > 代码库 > LeetCode:Unique Paths
LeetCode:Unique Paths
题目描述:
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?
思路:开一个m*n的数组pathCount,pathCount[i][j]表示从点(i,j)走到终点有多少种走法。将最后一列和最后一行的元素初始化为1(因为如果robot走到最后一列或者最后一行,将只能以一种方式走到终点)。根据pathCount[i][j]=pathCount[i+1][j]+pathCount[i][j+1],算出pathCount[0][0],即得到结果。
代码:
<pre name="code" class="cpp">int uniquePaths(int m, int n) { int ** pathCount = (int**)(malloc(sizeof(int*)*m)); int i,j; for(i = 0;i < m;i++) pathCount[i] = (int*)malloc(sizeof(int)*n); pathCount[m-1][n-1] = 0; for(i = 0;i < n;i++) pathCount[m-1][i] = 1; for(i = 0;i < m;i++) pathCount[i][n-1] = 1; for(i = m-2;i >= 0;i--) for(j = n-2;j >=0;j--) pathCount[i][j] = pathCount[i][j+1] + pathCount[i+1][j]; return pathCount[0][0]; }
LeetCode:Unique Paths
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。