Leetcode 62. 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?

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

Note: m and n will be at most 100.

思路：设定数组d，其中d[i][j]意味着到(i+1,j+1)的位置有的路径。显然当i==0或者j==0时，d[i][j]=1；其他条件下，d[i][j]=d[i-1][j]+d[i][j-1]。

代码：

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         int (*d)[100]=new int[100][100];
 5         int i,j;
 6         for(i=0;i<m;i++){
 7             d[i][0]=1;
 8         }
 9         for(i=0;i<n;i++){
10             d[0][i]=1;
11         }
12         for(i=1;i<m;i++){
13             for(j=1;j<n;j++){
14                 d[i][j]=d[i-1][j]+d[i][j-1];
15             }
16         }
17         return d[m-1][n-1];
18     }
19 };