算法进修Day-32

算法进修Day-32

63. 不同路径II

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

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

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

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

示例1

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

示例2

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

题解

由于每次只能向下或者向右移动，因此对于网格中的每个位置，到达该位置的路径数目需要通过相邻元素的路径数目计算得到。可以使用动态规划计算路径数目。

如果左上角 $obstacleGrid[0][0]$ 或右上角 $obstacleGrid[m-1][n-1]$ 为1时直接返回0

动态规划步骤如下

• 创建 $m\ast n$ 的二维数组 $dp$
• 当 $i=0,j=0$，路径 $(0,0)$ 上只有一个位置，路径数目为1，所以边界情况为 $dp[0][0]=1$
• 当 $i>0,j>0$，需要考虑如下方面
  • 当 $i=0,j>0$，只能从 $(i,j-1)$ 向右移动到 $(i,j)$，如果 $obstacleGrid[i][j]=0$ 则 $dp[i][j]=dp[i][j-1]$，如果 $obstacleGrid[i][j]=1$ 则 $dp[i][j]=0$
  • 当 $i>0,j=0$，只能从 $(i-1,j)$ 向下移动到 $(i,j)$，如果 $obstacleGrid[i][j]=0$ 则 $dp[i][j]=dp[i-1][j]$，如果 $obstacleGrid[i][j]=1$ 则 $dp[i][j]=0$
  • 当 $i>0,j>0$，可以从 $(i-1,j)$ 向下移动到 $(i,j)$ 或从 $(i,j-1)$ 向右移动到 $(i,j)$，如果 $obstacleGrid[i][j]=0$ 则 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$，如果 $obstacleGrid[i][j]=1$ 则 $dp[i][j]=0$

所以，当 $i>0$ 或 $j>0$，动态规划转移方程如下：
d p [ i ] [ j ] = { 0 , obstacleGrid[i][j]=1 d p [ i ] [ j − 1 ] , obstacleGrid[i][j]=0 & i=0 & j>0 d p [ i − 1 ] [ j ] , obstacleGrid[i][j]=0 & i>0 & j=0 d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] , obstacleGrid[i][j]=0 & i>0 & j>0 dp[i][j]=

{0,obstacleGrid[i][j]=1dp[i][j−1],obstacleGrid[i][j]=0 \& i=0 \& j>0dp[i−1][j],obstacleGrid[i][j]=0 \& i>0 \& j=0dp[i−1][j]+dp[i][j−1],obstacleGrid[i][j]=0 \& i>0 \& j>0" role="presentation" style="position: relative;">⎧⎩⎨⎪⎪⎪⎪⎪⎪0,dp[i][j−1],dp[i−1][j],dp[i−1][j]+dp[i][j−1],obstacleGrid[i][j]=1obstacleGrid[i][j]=0 \& i=0 \& j>0obstacleGrid[i][j]=0 \& i>0 \& j=0obstacleGrid[i][j]=0 \& i>0 \& j>0$$\{\begin{array}{ll}0,& \text{obstacleGrid[i][j]=1}\\ dp[i][j-1],& \text{obstacleGrid[i][j]=0 \& i=0 \& j>0}\\ dp[i-1][j],& \text{obstacleGrid[i][j]=0 \& i>0 \& j=0}\\ dp[i-1][j]+dp[i][j-1],& \text{obstacleGrid[i][j]=0 \& i>0 \& j>0}\end{array}$$

dp[i][j]=⎩ ⎨ ⎧​0,dp[i][j−1],dp[i−1][j],dp[i−1][j]+dp[i][j−1],​obstacleGrid[i][j]=1obstacleGrid[i][j]=0 & i=0 & j>0obstacleGrid[i][j]=0 & i>0 & j=0obstacleGrid[i][j]=0 & i>0 & j>0​

根据动态规划的状态转移方程，计算 $dp[i][j]$ 的顺序可以是一下两种

• 从小到大遍历每个 $i$，对于每个 $i$ 从小到大遍历每个 $j$。该顺序为按行遍历
• 从小到大遍历每个 $j$，对于每个 $j$ 从小大大便利每个 $i$。该顺序为按列遍历

计算得到 $dp[m-1][n-1]$ 即为从左上角到右上角的路径的最小值的和

想法代码

class Solution
{
    public static void Main(String[] args)
    {
        int[][] obstacleGrid =
        {
            new[]{0,0,0,0},
            new[]{0,1,0,0},
            new[]{0,0,0,0},
            new[]{0,0,1,0},
            new[]{0,0,0,0},
        };
        Solution solution = new Solution();
        int res = solution.UniquePathsWithObstacles(obstacleGrid);
        Console.WriteLine(res);
    }

    public int UniquePathsWithObstacles(int[][] obstacleGrid)
    {
        int m = obstacleGrid.Length, n = obstacleGrid[0].Length;
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1)
        {
            return 0;
        }
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n];
        }
        dp[0][0] = 1;
        for (int j = 1; j < n && obstacleGrid[0][j] == 0; j++)
        {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m && obstacleGrid[i][0] == 0; i++)
        {
            dp[i][0] = 1;
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                if (obstacleGrid[i][j] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}
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
43
44
45
46
47
48
49
50
51

64. 最小路径和

难度：中等
题目要求：
给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例1

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7

示例2

输入：grid = [[1,2,3],[4,5,6]]
输出：12

题解

由于每次只能向下或者向右移动，因此对于网格中的每个位置，到达该位置的路径数目需要通过相邻元素的路径数目计算得到。可以使用动态规划计算路径数目。

动态规划步骤如下

• 创建 $m\ast n$ 的二维数组 $dp$
• 当 $i=0,j=0$，路径 $(0,0)$ 上只有一个位置，最小路径和为 $grid[0][0]$，所以边界情况为 $dp[0][0]=grid[0][0]$
• 当 $i>0,j>0$，需要考虑如下方面
  • 当 $i=0,j>0$，只能从 $(i,j-1)$ 向右移动到 $(i,j)$，如果 $dp[i][j]=0$ 则 $dp[i][j]=grid[i][j]+dp[i][j-1]$
  • 当 $i>0,j=0$，只能从 $(i-1,j)$ 向下移动到 $(i,j)$，如果 $dp[i][j]=0$ 则 $dp[i][j]=grid[i][j]+dp[i-1][j]$
  • 当 $i>0,j>0$，可以从 $(i-1,j)$ 向下移动到 $(i,j)$ 或从 $(i,j-1)$ 向右移动到 $(i,j)$，到达 $(i,j)$ 最小路径和为两种情况的最小值，因此 $dp[i][j]=min(dp[i-1][j],dp[i][j-1]+dp[i][j-1])+grid[i][j]$

所以，当 $i>0$ 或 $j>0$，动态规划转移方程如下：
d p [ i ] [ j ] = { d p [ i ] [ j − 1 ] + g r i d [ i ] [ j ] , i=0 & j>0 d p [ i − 1 ] [ j ] + g r i d [ i ] [ j ] , i>0 & j=0 m i n ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) + g r i d [ i ] [ j ] , i>0 & j>0 dp[i][j]=

{dp[i][j−1]+grid[i][j],i=0 \& j>0dp[i−1][j]+grid[i][j],i>0 \& j=0min(dp[i−1][j],dp[i][j−1])+grid[i][j],i>0 \& j>0" role="presentation" style="position: relative;">⎧⎩⎨dp[i][j−1]+grid[i][j],dp[i−1][j]+grid[i][j],min(dp[i−1][j],dp[i][j−1])+grid[i][j],i=0 \& j>0i>0 \& j=0i>0 \& j>0$$\{\begin{array}{ll}dp[i][j-1]+grid[i][j],& \text{i=0 \& j>0}\\ dp[i-1][j]+grid[i][j],& \text{i>0 \& j=0}\\ min(dp[i-1][j],dp[i][j-1])+grid[i][j],& \text{i>0 \& j>0}\end{array}$$

dp[i][j]=⎩ ⎨ ⎧​dp[i][j−1]+grid[i][j],dp[i−1][j]+grid[i][j],min(dp[i−1][j],dp[i][j−1])+grid[i][j],​i=0 & j>0i>0 & j=0i>0 & j>0​

根据动态规划的状态转移方程，计算 $dp[i][j]$ 的顺序可以是一下两种

• 从小到大遍历每个 $i$，对于每个 $i$ 从小到大遍历每个 $j$。该顺序为按行遍历
• 从小到大遍历每个 $j$，对于每个 $j$ 从小大大便利每个 $i$。该顺序为按列遍历

计算得到 $dp[m-1][n-1]$ 即为从左上角到右上角的最小路径和

题解

class Solution
{
    public static void Main(String[] args)
    {
        int[][] grid =
        {
            new[] { 1, 3, 1 },
            new[] { 1, 5, 1 },
            new[] { 4, 2, 1 }
        };
        Solution solution = new Solution();
        int res = solution.MinPathSum(grid);
        Console.WriteLine(res);
    }

    public int MinPathSum(int[][] grid)
    {
        int m = grid.Length, n = grid[0].Length;
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i] = new int[n];
        }
        dp[0][0] = grid[0][0];
        for (int j = 1; j < n; j++)
        {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < m; i++)
        {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = Math.Min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
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