第三十九天| 62.不同路径、63. 不同路径 II

Leetcode 62.不同路径

题目链接：62 不同路径

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

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

思考一：动态规划。

确定dp数组（dp table）以及下标的含义

dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

确定递推公式

从dp[i][j]的定义可以看出，只能有两个方向来推导出来，即dp[i - 1][j]向右走和 dp[i][j - 1]向下走。

所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

dp数组的初始化

首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，dp[0][j]也同理。代码如下：

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

确定遍历顺序

从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1];中可以看出，dp[i][j]是依赖 dp[i - 1][j]和 dp[i][j - 1]，那么遍历的顺序一定是从左到右一层一层遍历的。

举例推导dp数组

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];       //记录到达下标（i，j）的路径数
        //初始化
        for (int i = 0; i < m; i++)     //从起始点一直到最右边只存在一条路径
            dp[i][0] = 1;
        for (int j = 0; j < n; j++)     //从起始点一直到最下边只存在一条路径
            dp[0][j] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];     //递推公式
        }
        return dp[m - 1][n - 1];
    }
};

优化：其实用一个一维数组（可以理解是滚动数组）即可，可以优化空间。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n);
        for (int i = 0; i < n; i++) dp[i] = 1;        //初始化
        for (int j = 1; j < m; j++) {
            for (int i = 1; i < n; i++) {        //处理每列元素
                dp[i] += dp[i - 1];
            }
        }
        return dp[n - 1];
    }
};

思考二：深度优先搜索。题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！如图：

但如果只是按以上思路同一位置多次计算，会超时。因此要加上备忘录，初始化为-1。终止条件加上判断当前位置备忘录是否记录过，记录过则直接返回数据。单层递归处理逻辑也要记录数据。

代码：

class Solution {
public:
    vector<vector<int>> memo;       //添加备忘录

    int dfs(int row, int col, const int m, const int n) {
        if (row > m || col > n) return 0;       //超出边界返回0
        if (row == m && col == n)   return 1;   //搜索到一条路径
        if (memo[row][col] != -1)   return memo[row][col];      //访问过则直接返回记录值

        int right = dfs(row + 1, col, m, n);        //向右移动
        int down = dfs(row, col + 1, m, n);         //向下移动
        memo[row][col] = right + down;      //记录数据
        return memo[row][col];  
    }

    int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) return 0;
        memo = vector<vector<int>>(m + 1, vector<int>(n + 1, -1));
        return dfs(1, 1, m, n);
    }
};

思考三：数论法。

在下图中，可以看出一共m，n的话，无论怎么走，走到终点都需要 m + n - 2 步。

在这m + n - 2 步中，一定有 m - 1 步是要向下走的，不用管什么时候向下走。

那么路径问题就转换为，给你m + n - 2个不同的数，随便取m - 1（或n - 1）个数，有几种取法。

这便是组合问题。答案为 $_{m+n-2}^{m-1}\textrm{C}$ 或 $_{m + n -2}^{n -1}\textrm{C}$ ，取较小值计算。

求组合要防止两个int相乘溢出。所以不能把算式的分子都算出来，分母都算出来再做除法。

代码：

class Solution {
public:
    int uniquePaths(int m, int n) {
        long long numerator = 1;       //分子
        int denominator = 1;           //分母
        int count = m > n ? n - 1 : m - 1;
        int num = m + n - 2;
        while (count > 0) {     //边乘边除
            numerator *= num;
            denominator *= count;
            if (denominator != 1 && numerator % denominator == 0) {     //可整除
                numerator /= denominator;
                denominator = 1;
            }
            num--;
            count--;
        }
        return numerator;
    }
};

Leetcode 63. 不同路径 II

题目链接：63 不同路径 II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

思考一：动态规划。

和上题的区别仅在障碍物，因此思路仅在确定递推公式和dp数组的初始化两步存在差异

确定递推公式

从dp[i][j]的定义可以看出，只能有两个方向来推导出来，即dp[i - 1][j]向右走和 dp[i][j - 1]向下走。

正常公式应为dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

但障碍物所在位置不可达，因此在处理前先判断。代码如下：

if (obstacleGrid[i][j] == 1)        //此下标位置存在障碍物    
    continue;

dp数组的初始化

由于障碍物的存在，因此只有在未碰到障碍物的前面位置dp[i][0]=1。dp[0][j]也同理。代码如下：

for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)     //从起始点向右直到碰到边界或者障碍物只存在一条路径
    dp[i][0] = 1;
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++)     //从起始点向下直到碰到边界或者障碍物只存在一条路径
    dp[0][j] = 1;

代码：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
	    if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍直接返回0
            return 0;
        vector<vector<int>> dp(m, vector<int>(n, 0));       //记录到达下标（i，j）的路径数   
        //初始化
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++)     //从起始点向右直到碰到边界或者障碍物只存在一条路径
            dp[i][0] = 1;
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++)     //从起始点向下直到碰到边界或者障碍物只存在一条路径
            dp[0][j] = 1;

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1)    continue;       //此下标位置存在障碍物
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];     //递推公式
            }
                
        }
        return dp[m - 1][n - 1];
    }
};

思考二：深度优先搜索。仅在终止条件这多加碰到障碍物则此条路径作废返回0即可。当然还得加上备忘录减少处理时间。

代码：

class Solution {
public:
    vector<vector<int>> memo;       //添加备忘录

    int dfs(int row, int col, const int m, const int n, const vector<vector<int>>& obstacleGrid) {
        if (row > m - 1 || col > n - 1) return 0;       //超出边界返回0
        if (obstacleGrid[row][col] == 1)    return 0;       //碰到障碍物返回0
        if (row == m - 1 && col == n - 1)   return 1;       //搜索到一条路径
        if (memo[row][col] != -1)   return memo[row][col];      //访问过则直接返回记录值

        int right = dfs(row + 1, col, m, n, obstacleGrid);      //向右
        int down = dfs(row, col + 1, m, n, obstacleGrid);       //向下
        memo[row][col] = right + down;      //记录数据
        return memo[row][col];
    }

    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        memo = vector<vector<int>>(m, vector<int>(n, -1));
        if (m < 1 || n < 1) return 0;
        return dfs(0, 0, m, n, obstacleGrid);
    }
};

自我总结：