题解 | #不同路径的数目(一)#

class Solution {
public:
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    int uniquePaths(int m, int n) {
        if (m < n) {
            swap(m, n);
        }
        long long res = 1;
        for (int i = m; i <= m + n - 2; ++i) {
            res = res * i / (i - m + 1);
        }
        return res;
    }
};

思路：组合数学。

一共需要向下走n - 1次，向右走m - 1次，共m + n - 2次。

即从m + n - 2次步数中选择n - 1次向下走，为C(n - 1) (m + n - 2)。