动态规划

题目-不同路径I

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为Start）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为Finish）。
问总共有多少条不同的路径？
62-1

示例1

  • 输入：m = 3, n = 7
  • 输出：28

示例2

  • 输入：m = 2, n = 3
  • 输出：3
  • 解释： 从左上角开始，总共有 3 条路径可以到达右下角。
    1. 向右 -> 向右 -> 向下
    2. 向右 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向右

示例3

  • 输入：m = 7, n = 3
  • 输出：28

示例4

  • 输入：m = 3, n = 3
  • 输出：6

《代码随想录》算法公开课
力扣题目链接

思路-I

首先机械人要到达终点必须要向下走n步，向右走m步，我们将机械人的初始位置表示为(0 , 0)，终点表示为(m-1 , n-1)。

动态规划五步曲-I

  1. 确定dp数组以及下标的含义
    dp[i][j] ：表示从(0 ，0)出发，到(i, j) 有dp[i][j]条不同的路径。

  2. 确定递推公式
    想要求dp[i][j]，只能有两个方向来推导出来，即从[i][j]位置的上方和左方移动而来，代码表示为dp[i - 1][j]和dp[i][j - 1]。

此时在回顾一下dp[i - 1][j]表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

  1. dp数组的初始化
    如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。

  2. 确定遍历顺序
    这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

  3. 举例推导dp数组
    62-2

代码实现-I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int uniquePaths(int m, int n) {
        //行列的索引都从0出发，则终点位置索引为[m-1][n-1]
        int[][] dp = new int[m][n];
        //初始化
        for(int i = 0; i < m; i++)dp[i][0] = 1;
        for(int i = 0; i < n; i++)dp[0][i] = 1;

        //因为每次只能向下或向右移动一步，则dp[i][j] 只能来自dp[i][j-1]向右移动一步，或者dp[i-1][j]向下移动一步
        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];
    }
}

题目-不同路径II

一个机器人位于一个m x n网格的左上角 （起始点在下图中标记为Start）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为Finish）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

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

示例1

  • 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  • 输出：2
  • 解释：3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：
    1. 向右 -> 向右 -> 向下 -> 向下
    2. 向下 -> 向下 -> 向右 -> 向右
      63-1

示例2

  • 输入：obstacleGrid = [[0,1],[0,0]]
  • 输出：1

《代码随想录》算法公开课
力扣题目链接

思路-II

首先这个题跟不同路径I很相似，则我们定义dp[i][j]为到达(i,j)的路径数，已知有障碍就无法通行，且dp数组会遍历到网格上的每一个点，则我们只需要令以障碍点为终点的路径删去就是没有障碍的路径，在这个思路中我们直接排除了含障碍点的路径。

动态规划五部曲-II

  1. 确定dp数组以及下标的含义
    dp[i][j]：表示从(0 ，0)出发，到(i, j)有dp[i][j]条不同的路径。

  2. 确定递推公式
    递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

注：但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。

  1. dp数组如何初始化
    在(i,0)不是障碍物之前，其路径数都是1，当(i,0)位置为障碍物之后，其路径数都为0.
1
2
3
4
5
6
for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
    dp[i][0] = 1;
}   
for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
    dp[0][j] = 1;
}

注：注意代码里for循环的终止条件，一旦遇obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，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]一定是有数值。

  2. 举例推导dp数组
    自己想象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];
        if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1)return 0;
        //遇到障碍物后面都是0,数组的初始值都是0
        for(int i = 0; i < m && obstacleGrid[i][0] != 1; i++){
            dp[i][0] = 1;
        }   
        for(int j = 0; j < n && obstacleGrid[0][j] != 1; j++){
           dp[0][j] = 1;
        }

        //dp数组会普及到每一个位置，只要当前是障碍物就直接不通，默认初始值为0
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = (obstacleGrid[i][j] == 0)? dp[i-1][j] + dp[i][j-1] : 0;
            }
        }
        return dp[m-1][n-1];
    }
}