本文共 1058 字，大约阅读时间需要 3 分钟。

Unique Paths

Total Accepted: 39541 Total Submissions: 120951 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. 这个题目可以不必使用动态规划，而使用数学中的组合方法来得到答案。 对于一个mxn的棋盘，机器人需要往右移动n-1次，往下移动m-1次， 我们令p = m-1（往下移动p次）;q=n-1（往右移动q次）; 我们可以把问题转换一下—用星号* 表示往右移动的事件，用|表示往下移动的事件。现在我们有p个|和q个*

*************

上面表示q个*

所有的路线情况可以想象为将p个|插入到上面q个*的序列中的所有情况。 这个数字为C(p,p+q) 用组合数学里面的隔板法可以得出这个结论。 所以这个题就转化为了计算c(p,p+q)也就是c(m-1,m+n-2)的值

class Solution {public:    int uniquePaths(int m, int n) {        --m;        --n;        if(m > n)            swap(m, n);        double result = 1;        for(int i = 0; i < m; ++i)        {            result = result * (m + n - i) / (i + 1);        }        return static_cast
   
    (result);    }};