[LeetCode 题解]: UniquePaths

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?

Note: m and n will be at most 100.Above is a 3 x 7 grid. How many possible unique paths are there?

提示：一个简单的组合数学问题。求 C(m+n-2,m-1). 区别于传统已知顶点，求路径的问题，从方格出发，需要注意m-1, n-1的问题。

解法一：使用vector，用于保存尚未处理的除数，用于动态保存。

 1 class Solution {
 2 public:
 3     int uniquePaths(int m, int n) {
 4         if(m*n==0 || m==1 || n==1 ) return 1;  
 5         
 6         m--;
 7         n--;
 8         
 9         vector<int> vi;
10         vector<int>::iterator iter;
11         int i=m+n,j,ans=1;
12 
13         m = (m<n?m:n);
14         for(j=m;j>=1;j--)
15           vi.push_back(j);
16 
17         for(j=m;j>0;j--)
18         {
19            ans*=i;
20            if(!vi.empty())
21            {
22                iter= vi.begin();
23                while(iter!=vi.end())
24                {
25                    if(ans%(*iter)==0)
26                    {
27                        ans/=(*iter);
28                        vi.erase(iter);
29                        if(vi.empty())
30                             break;
31                        iter--;
32                    }
33                    iter++;
34                }
35            }
36            i--;
37         }
38         return ans;
39     }
40 };

解法二：简约版，采用变量增长特性。

 1     int uniquePaths(int m, int n) {
 2         m--; n--;
 3         if(m<0 || n<0) return 0;
 4         if (m==0 || n==0) return 1;
 5 
 6         int i=m+n, j=1, ans=1;
 7         m=(m<n?m:n);
 8         n=i-m;
 9         for(i=m+n,j=1; i>n;i--)
10         {
11             ans*=i;
12             for(;j<=m && ans%j==0; j++)
13                 ans/=j;
14         }
15         return ans;
16     }