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.

题目大意

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

思路

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

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

提交结果
提交结果