62. 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 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

　　题目要求到达终点的可能路径，在已知长宽的情况下，到达途中Finish，一共要走(m - 1) + ( n - 1) = m + n - 2，其中向右m - 1步，向下n - 1步，很典型的排列组合问题，即在m + n - 2步中选 m - 1个位置向右走，剩下的自然是向下走，得到公式：

　　　　N = C（m + n - 2, m - 1）

　　编码完成组合公式的计算：

    public int uniquePaths(int m, int n) {
        return choose(m + n - 2, m > n ? n - 1 : m - 1);
    }

    public static int choose(int m, int n) {
        int member = 1;
        int temp = n;
        while (temp-- > 0) {
            member *= m--;
        }
        int denominator = 1;
        int start = 1;
        temp = n;
        while (temp-- > 0) {
            denominator *= start++;
        }
        return member / denominator;
    }

　　提交后发现，在case : m = 10 , n = 10时，未通过。想了半天确定解题思路没问题，于是一步步debug，终于发现乘法计算中，超出了int能表示的最大整数！

　　换种写法：

    public static int choose(int m, int n) {
        long result = 1;
        for (int i = 0; i < n; i++) {
            result = result * (m - i) / (i + 1);
        }
        return (int) result;
    }

　　注意这里写成：

    result *= (m - i) / (i + 1);

　　答案依然会不对，因为：

result *=  (m - i) / (i + 1) 等同于result = （m - i）/(i + 1)*result;

　　而答案中的写法其实是发生了自动转型的，即long * int -> long * long。

　　额，上面那段鬼话，差点把自己也骗过去了，其实写这段字的时候我就一直有个疑问，不管是long还是int，都只能表示整数，而除法（m - i）/(i + 1)是明显会产生余数而被近似的，为什么最终却能产生正确答案？

　　回过头来看数学里的组合公式（即C(m,n)）同样也有这样的问题，物理意义上组合是不存在小数种选择的，但是，这是个带除法的公式，是怎么保证结果一定是整数的？

　　这里把公式的计算过程展开就很容易看出原因了，字母不好写，我直接以实际例子做演示：

　　例如C（19 ，5），通过公式展开可知道结果为：（19*18*17*16*15）/（1*2*3*4*5），这里如果变成(19/1 ) * (18/2) *(17/3) *(16/4) * (15/5) 即是代码中result = （m - i）/(i + 1)*result的运算方式，明显可以看到（17/3）是无法整除的。但是，单独观察19/1 ) * (18/2) *(17/3) 这部分，运算开始时19/1，一定是整数，当18/2的时候，这时分子有19 * 18，分母是1 * 2，其中，2虽然不能被任何数整除，但是按照公式展开的方式

　　当我们要除分母中的n时，分子此时一定可以写成n个连续的数相乘，既然分子已经是n个连续数相乘（循环了一个n周期），那么这n个数中一定存在一个数可以整除分母中的n。

　　在上面的例子里17/3虽然不能整除，但是19*18*17/（1*2*3），3个数中必然存在一个数（这里是18）可以除尽3。

　　这才是为什么代码里必须写成result = result * (m - i) / (i + 1)，而不是先除后乘的形式result = （m - i）/(i + 1)*result ！！！

　　当然这题目其实也可以用dp，从finish点向前推一步，可以得到:

　　　　1、机器人在向右一步才到达终点，即dp[m-1][n] -> right ；

　　　　2、机器人向下一步才到达终点，即dp[m][n-1] -> down。

　　由上容易知道dp方程为： dp[m][n] = dp[m-1][n] + dp[m][n-1] ，另外dp[1[n] = dp[m][1] = 1。

    public static int uniquePaths2(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == 1 || j == 1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }