Leetcode 62. Unique Paths

62. Unique Paths

Total Accepted: 93894
Total Submissions:253450
Difficulty: Medium

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>=0,j>=0)意味着到(i+1,j+1)的位置有的路径。显然当i==0或者j==0时，d[i][j]=1；其他条件下，d[i][j]=d[i-1][j]+d[i][j-1]。

方法二：从排列组合的角度出发，d[i][j]=C(i+j,i)=C(i+j,j)。

代码：

方法一：

没有优化之前的代码，空间复杂度是m*n。

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

其实，

1. (i,0)和(0,j)（其中0<=i<m，0<=j<n）的路径数=1。所以初始化vector的元素都为1。

2. (i,j)路径数（i!=0||j!=0）=(i-1,j)路径数+(i,j-1)路径数。所以只要一个vector记录(i,j)的路径数，其中vector元素坐标只与j有关。

优化以后的代码：空间复杂度是2*max(m,n)

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         vector<int> cur(n,1);//初始化为n个1
 5         int i,j;
 6         for(i=1;i<m;i++){
 7             for(j=1;j<n;j++){
 8                 cur[j]+=cur[j-1];
 9             }
10         }
11         return cur[n-1];
12     }
13 };

方法二：
关于循环中的乘积为什么这么写，暂时没有想清楚。

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         int N=m-1+n-1;
 5         int k=m-1;
 6         int i;
 7         double pro=1;
 8         for(i=1;i<=k;i++){
 9             pro=pro*(N-k+i)/i;//改成pro*=(N-k+i)/i;结果就是错的 
10         }
11         return round(pro);
12     }
13 };