Unique Paths

Description:

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?

Code:

 1  int uniquePaths(int m, int n) {
 2         //空间复杂度：O(MN)
 3         assert(m<=100 && n<=100);
 4         
 5         int path[MAX+1][MAX+1] = {0};//有效数字下标从1开始，便于阅读，因此这里加1
 6         for (int i = 1; i <= m; ++i)
 7         {
 8             path[i][1] = 1;
 9         }
10         for (int i = 1; i <= n; ++i)
11         {
12             path[1][i] = 1;
13         }
14         
15         for (int i = 2; i <= m; ++i)
16         {//因为m或n为1时的路径数都为1，所以不用再考虑
17             for (int j = 2; j <= n; ++j)
18             {
19                 path[i][j] = path[i-1][j] + path[i][j-1];
20             }
21         }
22         return path[m][n];
23     }