62题目

一个只能向右走或向下走的机器人位于左上角，要到右下角，有多少种唯一的路径？

机器人路径
机器人路径

Example 1:

1
2
3
4
5
6
7
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

1
2
Input: m = 7, n = 3
Output: 28

62分析

62这道题可以完全不用动态规划， 利用简单的排列组合也能解决问题 。 但是为了引出63， 还是给出动态规划的解法。

排列组合

通过观察， 总结规律， 我们可以知道， 结果和行、列关系如下

$$result = \frac{(m-1+n-1)!}{(m-1)!(n-1)!}$$

可能你看这个公式会有点懵， 但是， 结合图片可以分析到， 当迷宫是7*3时，我们势必要走两个 down($n-1$)和 6($m-1$) 个 right ，于是就变成了$C_8^2$或者你也可以认为$C_8^6$

下面排列组合的代码中， 可以关注一下关于排列组合的运算代码

动态规划

在前面的动态规划我们提到， 动态规划需要有一个存储结构， 即所谓的“记忆性”， 应用在这道题目上面， 记忆性便是指当前方格的唯一路径数。
在程序上，我们首先遍历两个边界，也就是第一行和第一列，将他们全部置为 1（由于机器人只能向下和向右，所以边界的不重复路径只有一条），然后我们遍历其他方块， 方块的可达路径数等于他上面的方块路径数 + 他左面的方块的路径数， 即

$$res[i][j]=res[i-1][j]+res[i][j]$$

计算到右下角， 右下角的路径数即为最终结果

代码

排列组合代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        m--;
        n--;
        if(m < n) {              // Swap, so that m is the bigger number
            m = m + n;
            n = m - n;
            m = m - n;
        }
        long res = 1;
        int j = 1;
        for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
            res *= i;
            res /= j;
        }
        return (int)res;
    }
}

动态规划代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int uniquePaths(int m, int n) {
        Integer[][] map = new Integer[m][n];
        for(int i = 0; i<m;i++){
            map[i][0] = 1;
        }
        for(int j= 0;j<n;j++){
            map[0][j]=1;
        }
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                map[i][j] = map[i-1][j]+map[i][j-1];
            }
        }
        return map[m-1][n-1];
    }
}

63题目

这次题目在 62 的基础上稍微有些修改 ，机器人的走法不变， 但是地图会出现障碍物， 给定一个 m*n 二维数组， 0 表示没有障碍物， 1 表示此路不通。

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right

63分析

这种情况下，显然我们的排列组合方法就不适用了， 继续用动态规划问题解决， 我们仍然采取“记忆法”：

首先，检查左上角元素是不是阻挡快 ，如果不是阻挡块（0），则更新为 1 ，这个 1 的含义就是 62 中的可达路径数（下面简称路径数）。

然后 ，遍历两个边界， 这个时候比 62 题多了一个判断， 如果前一个是 1（路径数）（注意：这个 1 不是阻挡块的 1 而是更新后的路径数 ，而自己是 0 （未更新，非阻挡块），则将它置为 1，否则置为 0 。

过程图：

初始状态
初始状态

遍历行边界
遍历行边界

遍历列边界
遍历列边界

遍历全部
遍历全部

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        int R = obstacleGrid.length;
        int C = obstacleGrid[0].length;

        // If the starting cell has an obstacle, then simply return as there would be
        // no paths to the destination.
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // Number of ways of reaching the starting cell = 1.
        obstacleGrid[0][0] = 1;

        // Filling the values for the first column
        for (int i = 1; i < R; i++) {
            obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
        }

        // Filling the values for the first row
        for (int i = 1; i < C; i++) {
            obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
        }

        // Starting from cell(1,1) fill up the values
        // No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
        // i.e. From above and left.
        for (int i = 1; i < R; i++) {
            for (int j = 1; j < C; j++) {
                if (obstacleGrid[i][j] == 0) {
                    obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
                } else {
                    obstacleGrid[i][j] = 0;
                }
            }
        }

        // Return value stored in rightmost bottommost cell. That is the destination.
        return obstacleGrid[R - 1][C - 1];
    }
}

更多动态规划问题

更多动态规划问题关注标签：动态规划