首页 > 代码库 > 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