题目

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：*m 和 n* 的值均不超过 100。

示例 1:

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

示例 2:

1 2	输入: m = 7, n = 3 输出: 28

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:

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

解题方法

动态规划

设到达点$(a,b)$的不同路径数为$N(a,b)$。

到达$(m, n)$点的之前的一步只有$(m-1, n)$和$(m, n-1)$两种。

所以状态转移：$N(m,n)=N(m-1, n)+N(m,n-1)$。

初始条件：第一行或者第一列的点只有一种不同路径可到达。

这段代码1ms，超过了85.72%的Java提交。

class Solution {
    // Method 1 1ms 85.72%
    public int uniquePaths(int m, int n) {
        int [][] mat = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = i == 0 || j == 0 ? 1 : mat[i - 1][j] + mat[i][j - 1];
            }
        }
        return mat[m - 1][n - 1];
    }
}

排列组合

到达点$(m,n)$需要向下走$m-1$步，向右走$n-1$步，一共$m+n-2$步，可以看成是总步数中，哪$m-1$步是向下走的，是一个组合问题，一共$C(m+n-2,m-1)$种走法。这段代码跑了1ms，超过了100%的Java提交。

class Solution {
    // Method 2 0ms 100%
    public int uniquePaths(int m, int n) {
        // C(m+n-2,n-1) = C(m+n-2,m-1)
        int sum = m + n -2;    // total steps
        int down = n - 1;    // down steps
        double res = 1;
        for(int i = 1;i <= down; i++){
            res =res * (sum - down + i) / i;
        }
        return (int)res;
    }
}