一个机器人站立在 m×n 方格的左上角（下图中标记为“Start”的位置）。

这个机器人只能向右或向下移动。机器人正在试着移动到方格的右下角（下图中标记为“Finish”的位置）。

共有多少条不同的路径可以移动？

上图是 7×3 的方格，共有多少种可能的路径？

提示： m 与 n 最大为 100。

例一：
输入： m = 3, n = 2
输出： 3
解释：
从左上角开始，共有 3 条路径可以到达右下角：
1. 右->右->下
2. 右->下->右
3. 下->右->右

例二：
输入： m = 7, n = 3
输出： 28

这个题也很有意思，猛的一看很简单，就是一个数理统计问题嘛。

对于这个题，我们当然可以用数学方法去解，这也是大多数人第一次遇到这个问题的想法。同时这个题我们也可以用动态规划来解。

思考一下便可知，从起点到达某一个位置的路径数量，等于 从起点到达其左边的位置的路径数量 与 从起点到达其上边的位置的路径数量 之和。而当这个位置在第一行或第一列时，路径数量为确定的 1，这样我们就可以递归把任意位置的路径数量算出来。

/*
 * 62. Unique Paths
 * https://leetcode.com/problems/unique-paths/
 * https://www.whosneo.com/62-unique-paths/
 */

public class UniquePaths {
    public static void main(String[] args) {
        UniquePaths solution = new UniquePaths();

        System.out.println(solution.uniquePaths(4, 5));
        System.out.println(solution.uniquePaths(5, 5));
        System.out.println(solution.uniquePaths(8, 4));
    }

    private int uniquePaths(int m, int n) {
        if (m == 0 || n == 0)
            return 0;

        // 只能横向或只能纵向移动时，路径只有一种
        if (m == 1 || n == 1)
            return 1;

        int[][] result = new int[m][n];

        // 接下来，其余位置的移动路径的数量等于
        // 其上方位置的路径 与 其左方位置的路径 的和
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)
                    result[i][j] = 1;
                else
                    result[i][j] = result[i][j - 1] + result[i - 1][j];
            }

        return result[m - 1][n - 1];
    }

    // 仅使用一维数组存储，降低空间复杂度
    private int uniquePaths2(int m, int n) {
        if (m == 0 || n == 0)
            return 0;

        // 只能横向或只能纵向移动时，路径只有一种
        if (m == 1 || n == 1)
            return 1;

        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        }

        int[] result = new int[n];

        for (int i = 0; i < m; i++)
            for (int j = 0; j < n && j <= i; j++) {
                if (j == 0)
                    result[j] = 1;
                else if (i == j)
                    result[j] = result[j - 1] * 2;
                else
                    result[j] = result[j - 1] + result[j];
            }

        return result[n - 1];
    }
}