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

数学排列组合题。向左和向右走的步数总共是(m + n - 2)，总步数全排列是(m + n - 2)!，其中每种走法重复(m - 1)! * (n - 1)!次。

所以不同的走法共：(m + n - 2)! / (m - 1)! / (n - 1)!。

public class Solution {
    /**
     * 数学运算表达式：(m + n - 2)! / (m - 1)! / (n - 1)!
     * @param m int整型
     * @param n int整型
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        int totalSteps = m + n - 2;// 总步数

        int min = Math.min(m - 1,n - 1);// 最小迭代累乘次数

        long a = 1, b = 1;
        while (min > 0){
            a *= totalSteps--;
            b *= min--;
        }

        return (int)(a / b);
    }
}