题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
说明： m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
解题思路
和爬楼梯问题的思路类似，使用动态规划法解决。
设到达终点的路径数目为F(m,n)，F(m,n)只与前两个状态有关，即走到(m,n)点的路径数等于走到(m-1,n)的路径数加上走到(m,n-1)的路径数目，用递推公式表示就是F(m,n) = F(m-1,n)+F(m,n-1)。
想要知道F(m-1,n)就要知道F(m-2,n)和F(m-1,n-1)，同理，想要知道F(m,n-1)就要知道F(m-1,n-1)和F(m,n-2)，如此递推下去，到边缘，我们知道了F(0,0),F(0,1),F(1,0)就可以知道所有的 F 值。而我们可以直接得到：
F(0,0) = 1;
F(0,1) = 1;
F(1,0) = 1;
因为机器人只能向下或者向右走，所以实际上F(0,n) = 1以及F(m,0) = 1，这就是初始化条件。我们再自底向上解决问题，使用一个二维数组存放 F 值，直到得到最后的F(m,n)。
Java 实现
public int uniquePaths (int m, int n) {
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
matrix[i][0] = 1;
}
for (int j = 0; j < n; j++) {
matrix[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
}
}
return matrix[m - 1][n - 1];
}
心得体会
本题实际上就是爬楼梯问题的二维化，关于爬楼梯问题，可以参考我之前写过的一篇文章。