LeetCode 62 - Unique Paths

作者 QIFAN 日期 2017-01-05
LeetCode 62 - Unique Paths

原题链接:62. Unique Paths


题干

有一个 m * n 的矩阵,有一个小机器人在左上角,它只能往下或往右走,问到达右下角一共有多少不同的路径?

思路

首先可以确定,一共要走 m + n 步。

要用动态规划的话,需要思考当前的状态,以及与上一个状态有什么关联?然后有了一个关系等式,问题就迎刃而解。

假设某一个状态,小机器人在 (i, j) 位置,此时走了 i + j 步。他的上一个位置可能在 (i - 1, j) 或者 (i, j - 1) 。那此时可能的不同路径数就是 (i - 1, j) 和 (i, j - 1) 处路径数之和。那关系就出来了:

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

怎么走需要思考一下,因为除了原点,每个点都有很多不确定的路径。所以只能按照广度优先。

代码:

public int uniquePaths(int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (m == 1 || n == 1) {
return 1;
}
int[][] dp = new int[m][n];
// 设定原点路径数为 1
dp[0][0] = 1;
// 广度优先遍历
for (int step = 1; step <= m + n; step++) {
int i = 0;
int j = step - i;
// 保证小机器人在矩阵内
while (i < m && j >= 0) {
if (j < n) {
if (i == 0) {
dp[i][j] = dp[i][j - 1];
} else if (j == 0) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
i++;
j = step - i;
}
}
return dp[m - 1][n - 1];
}