代码随想录算法训练营第三十九天 | 不同路径 I II

62. 不同路径

leetcode
文档题解
视频题解

决策题，暴力回溯，超时，淦！

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

leetcode
文档题解
视频题解

思路和上一题一样，区别就是 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];
    }
}