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?

示例图
示例图

Note: m and n will be at most 100.

题目大意

给定两个数字m和n作为一个长方形的长和宽，一个机器人从左上角开始，每次只能往右或者往下走，问到达长方形最左下角一共有多少种走法？

思路

很明显是一个二维的动态规划题。动态规划最重要的就是要找到递推式，将当前的大问题划分为更小的子问题。

以3x7的格子为例，对于坐标为(2,5)的格子，只有可能是从上面(1,5)或者左边(2,4)的格子到达。那么到达这个格子的走法应当是到达(2,4)和到达(1,5)两个格子的走法之和。那么我们就得到了递推式

1
D(i, j) = D(i - 1, j) + D(i, j - 1)

当然我们还需要考虑一些特殊情况。当格子在第一行即i = 0时，只能由左边的格子到达；当格子在第一列即`j = 0’时，只能由上方的格子到达。其实这两个特殊情况中的格子都只有一种走法到达。

这种思路需要使用m x n的空间用来存储所有格子的走法总数，同时需要遍历整个格子，因此空间复杂度和时间复杂度都是O(m*n)。Java版的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int uniquePaths(int m, int n) {
        int [][] number = new int [m][n];

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (i == 0 || j == 0) {
                    number[i][j] = 1;
                } else {
                    number[i][j] = number[i - 1][j] + number[i][j - 1];
                }
            }
        }
        return number[m - 1][n - 1];
    }
}

Leetcode提交运行时间为1ms

提交结果
提交结果