LeetCode-062-不同路径

Posted on | In | Views:

LeetCode-062-不同路径

1. 题目：

不同路径

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

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

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

img

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

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

示例 1:

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

示例 2:

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

2. 解题：

​ 使用动态规划，我们假设path(i,j)表示从(i,j)位置到达终点的不同路径数。

​ 我们知道如果想知道path(0,0)点的路径数，我们可以用path(1,0) + path(0,1)来求出其路径数，因此我们得到一个递推公式：path(i,j) = path(i+1,j) + path(i,j+1).

​ 我们发现path(1,0) = path(2,0) + path(1,1)和path(0,1) = path(1,1) + path(0,2)其中重复使用了path(1,1)因此我们需要记录每一个位置路径数，防止重复计算。

​ 我们还发现，每次计算一个位置时，需要的是其下方和右方的位置，因此我们可以“自底向上”就是从终点出发，这样方便我们计算。

​ 我们知道终点位置路径数为1，这样我们可以计算其上方，和其右方的位置，一次类推，我们可以求出起点位置的路径数。

​ 我们需要注意边界问题，若当前位置没有下方或右方时，用0代替。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public static int uniquePaths(int m, int n) {
        if (m <=0 || n <= 0)
            return 0;

        int[][] paths = new int[m][n];
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i == m-1 && j == n-1) {
                    paths[i][j] = 1;
                    continue;
                }
                int A = (i+1 < m) ? paths[i+1][j] : 0;
                int B = (j+1 < n) ? paths[i][j+1] : 0;
                paths[i][j] = A+B;
            }
        }
        return paths[0][0];
    }
}