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.
思路：
这道题当然可以用有向图搜索的方法来解决。但是有没有更简单的办法呢？
因为机器人只能向固定的两个方向移动，所以向右，向下移动的次数都是固定的，总共移动的次数也是固定的。一旦确定向右（向下）移动发生在哪几部，剩下的移动必然是向下（向右）的。
所以只要做一个组合计算就可以了。机器人本身在（1，1）处，所以需要去掉两步从（0，0）到（1，1）的移动。
组合计算由于包含阶乘，所以需要特别小心溢出。这里的方法选自TAOCP。
题解：
class Solution {
public:
unsigned long long
choose(unsigned long long n, unsigned long long k) {
if (k > n) {
return 0;
}
unsigned long long r = 1;
for (unsigned long long d = 1; d <= k; ++d) {
r *= n--;
r /= d;
}
return r;
}
int uniquePaths(int m, int n) {
if (m == 1 || n == 1)
return 1;
if (m < n) swap(m, n);
return choose(m+n-2, n-1);
}
};