62. 不同路径
决策题,暴力回溯,超时,淦!
class Solution {
int count = 0;
public int uniquePaths(int m, int n) {
backtrace(m, n, 0, 0);
return count;
}
public void backtrace(int m, int n, int i, int j) {
// 越界
if (i >= m || j >= n) return;
// 到达右下角
if (i == m - 1 && j == n - 1) {
count++;
return;
}
// k == 1:往下走,k == 2:往右走
for (int k = 1; k <= 2; k++) {
backtrace(m, n, k == 1 ? i + 1 : i, k == 1 ? j : j + 1);
}
}
}
动态规划!
class Solution {
public int uniquePaths(int m, int n) {
// dp[i][j] 表示到达 i,j 位置有几种解法
int[][] dp = new int[m][n];
// 因为机器人在左上角,目的地在右下角
// 并且机器人只能往右或往下走
// 所以到达 i,j 的方向有两个:[i, j - 1] 和 [i - 1, j]
// 因此状态转移方程: F(i, j) = F(i, j - 1) + F(i - 1, j)
// 初始化 dp
dp[0][0] = 1;
// 遍历 dp,因为要知道左和上的状态,所以朝右和下的方向遍历
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i - 1 >= 0) {
dp[i][j] += dp[i - 1][j];
}
if (j - 1 >= 0) {
dp[i][j] += dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
上面没有严格按照递推公式来求 dp 数组的值,比较规范的写法是这样的,dp 数组的初始化也略有不同。
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// dp 初始化,第一行以及第一列初始化为 1
// 因为这两个部分的值无法直接从递推公式计算
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// 遍历 dp
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 直接从递推公式计算 dp 数组
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}
时间复杂度:O(m n)
空间复杂度: O(m n)
63. 不同路径 II
思路和上一题一样,区别就是 dp 的初始化,障碍物及其之后的位置的 dp 值都是 0。而且在使用递推公式时不需要判断左边和上边是否是障碍物,即便是,dp 值也是 0,按照递推公式相加也没问题。
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
// 如果有障碍,后面的就不初始化了
dp[i][0] = 1;
}
for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
// 如果有障碍,后面的就不初始化了
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 有障碍,就不用计算了
if (obstacleGrid[i][j] == 1) continue;
// 直接使用递推公式,有障碍物的 dp 是 0,加了也无妨
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m - 1][n - 1];
}
}