Solution to LeetCode Problems: Unique Paths

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.


Thoughts:
Of course, this can be solved by applying either DFS or BFS on a directed graph. Any better solution?
Since the robot can only choose "right" or "down", the total number of each movement are fixed to (m+n-2). We can first pick up (m-1) "down" moves, and the other movements can be "right" direction only.
So the total number of unique paths are Combination(m+n-2, m-1).
The combination has factorial calculations, so we have to be careful avoiding overflow. Here the algorithm is taken from TAOCP.

Solution:

1. class Solution {  
2. public:  
3.     unsigned long long  
4.     choose(unsigned long long n, unsigned long long k) {  
5.         if (k > n) {  
6.             return 0;  
7.         }  
8.         unsigned long long r = 1;  
9.         for (unsigned long long d = 1; d <= k; ++d) {  
10.             r *= n--;  
11.             r /= d;  
12.         }  
13.         return r;  
14.     }  
15.   
16.     int uniquePaths(int m, int n) {  
17.         if (m == 1 || n == 1)  
18.             return 1;  
19.               
20.         if (m < n) swap(m, n);  
21.           
22.         return choose(m+n-2, n-1);         
23.     }  
24. };