likes
comments
collection
share

矩阵中的二维动态规划🐾

作者站长头像
站长
· 阅读数 40

只考虑向下走

120. 三角形最小路径和

120. 三角形最小路径和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

 

示例 1：

输入： triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出： 11
解释： 如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

示例 2：

输入： triangle = [[-10]]
输出： -10

 

提示：

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • −104<=triangle[i][j]<=104-10^4 <= triangle[i][j] <= 10^4−104<=triangle[i][j]<=104

 

进阶：

  • 你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题吗？

分析

我们把那个三角形换成这样，每次只能向下或者向右走一步。

矩阵中的二维动态规划🐾

dp[i][j]dp[i][j]dp[i][j]表示triangle[i][j]triangle[i][j]triangle[i][j]位置的最小路径和

按照题意就是 dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+triangle[i][j]dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+triangle[i][j]

注意判断边界！

  • 最左边的一列是取不到dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]的

  • 对角线那一列取不到dp[i−1][j]dp[i-1][j]dp[i−1][j]

矩阵中的二维动态规划🐾

最终的动态规划：

  • 边界条件：dp[0][0]=triangle[0][0]dp[0][0] = triangle[0][0]dp[0][0]=triangle[0][0]

  • 递推公式：

    • 最左边：dp[i][j]=dp[i−1][j]+triangle[i][j]dp[i][j] = dp[i-1][j] + triangle[i][j]dp[i][j]=dp[i−1][j]+triangle[i][j]

    • 中间：dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+triangle[i][j]dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])+triangle[i][j]

    • 最右边：dp[i][j]=dp[i−1][j−1]+triangle[i][j]dp[i][j] = dp[i-1][j-1] + triangle[i][j]dp[i][j]=dp[i−1][j−1]+triangle[i][j]

最后要注意结果，因为限定了dp[i][i]的来源范围，最后一个元素不一定是最下的下降路径和，我们要从最后一行中取最小值作为结果。

代码

代码如下：

class Solution:
    def minimumTotal(self, triangle) -> int:
        '''
        dp[i][j]表示triangle[i][j]位置的最小路径和
        dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
        注意判断边界！
        '''
        n = len(triangle)
        dp = [[0] * (i + 1) for i in range(n)]  # 建立和三角形同形状的dp数组
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            for j in range(i + 1):
                if j == 0:
                    dp[i][j] = triangle[i][j] + dp[i - 1][j]
                elif i == j:
                    dp[i][j] = triangle[i][j] + dp[i - 1][j - 1]
                else:
                    dp[i][j] = triangle[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1])
        return min(dp[-1])


triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]
Solution().minimumTotal(triangle)

该函数的时间复杂度为 O(n2)O(n^2)O(n2)，其中 nnn 是数字三角形的行数，因为它遍历数字三角形中的每个元素一次，并对每个元素执行常数时间操作。空间复杂度也为 O(n2)O(n^2)O(n2)，因为它创建了一个与输入数字三角形大小相同的 dp 列表。

进阶优化：

class Solution:
    def minimumTotal(self, triangle) -> int:
        '''
        dp[i][j]表示triangle[i][j]位置的最小路径和
        dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]) + triangle[i][j]
        注意判断边界！
        '''
        n = len(triangle)
        dp = [[0] * n, [0] * n]  # 建立和三角形同形状的dp数组
        dp[0][0] = triangle[0][0]
        for i in range(1, n):
            for j in range(i + 1):
                if j == 0:
                    dp[i % 2][j] = triangle[i][j] + dp[i % 2 - 1][j]
                elif i == j:
                    dp[i % 2][j] = triangle[i][j] + dp[i % 2 - 1][j - 1]
                else:
                    dp[i % 2][j] = triangle[i][j] + min(dp[i % 2 - 1][j], dp[i % 2 - 1][j - 1])
        return min(dp[-1])

这段代码是一个优化版本的动态规划解法，与原始的解决方案不同的是，它使用一个大小为 2 的滚动数组，而不是一个大小为 nnn 的二维数组来存储每个位置的最小路径和。具体来说，它仅使用 dp 列表中的两行来计算当前行的最小路径和，因此只需要为 dp 列表分配两个列表。在每次迭代中，它使用当前行的索引对 2 取模，以确定要更新哪个列表。

此外，该函数在处理每行的第一个和最后一个元素时，不需要特殊处理，因为它使用了 % 运算符来确保 dp 列表中的索引始终在有效范围内。

该函数的时间复杂度仍然为 O(n2)O(n^2)O(n2)，因为它遍历数字三角形中的每个元素一次，并对每个元素执行常数时间操作。但是，该函数的空间复杂度为 O(n)O(n)O(n)，因为它只使用了大小为 2 的 dp 列表来存储最小路径和。

931. 下降路径最小和

931. 下降路径最小和

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 **的 ****最小和 。

下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

 

示例 1：

矩阵中的二维动态规划🐾

输入： matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出： 13
解释： 如图所示，为和最小的两条下降路径

示例 2：

矩阵中的二维动态规划🐾

输入： matrix = [[-19,57],[-40,-5]]
输出： -59
解释： 如图所示，为和最小的下降路径

 

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 100
  • -100 <= matrix[i][j] <= 100

代码

这个题和上一题的思路完全一样，所以不用分析了，直接上代码：

class Solution:
    def minFallingPathSum(self, matrix) -> int:
        '''
        d[i][j]表示下降到当前位置的最小路径和
        dp[i][j] = matrix[i][j] + min(dp[i-1][j-1:j+1])
        '''
        m, n = len(matrix), len(matrix[0])

        dp = [[0] * n for _ in range(m)]
        dp[0] = matrix[0]

        for i in range(1, m):
            for j in range(n):
                dp[i][j] = matrix[i][j] + \
                           min(dp[i - 1][j],
                               dp[i - 1][max(0, j - 1)],
                               dp[i - 1][min(j + 1, n - 1)])
        return min(dp[-1])

该函数的时间复杂度为 O(mn)O(mn)O(mn)，其中 mmm 和 nnn 分别为矩阵的行数和列数。因为该函数遍历矩阵中的每个元素一次，并对每个元素执行常数时间操作。该函数的空间复杂度为 O(mn)O(mn)O(mn)，因为它创建了一个大小和矩阵相同的二维数组来存储最小下降路径和。

考虑向下和向右

64. 最小路径和

64. 最小路径和 - 力扣（Leetcode）

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

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

 

示例 1：

矩阵中的二维动态规划🐾

输入： grid = [[1,3,1],[1,5,1],[4,2,1]]
输出： 7
解释： 因为路径 1→3→1→1→1 的总和最小。

示例 2：

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

 

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100

分析

只能向下或者向右走。

矩阵中的二维动态规划🐾

初始我们在[0][0][0][0][0][0]是无法选择的。

我们在第一行某一个格子的时候，因为上边没有元素，所以只能是从左边过来的，所以第一行也是别无选择的，只能和左边的数值相加，第一列同理，左边没有元素，所以只能从上边往下走，只能是第一列的元素相加。

其他位置的格子可以从上边或者左边过来，因为要求最小路径和，所以要找从哪条位置过来的数值最小就选择哪条路。

动态规划过程:

  • 边界条件：dp[0][0]=grid[0][0]dp[0][0] = grid[0][0]dp[0][0]=grid[0][0]

  • 递推公式：

    • 第一行：dp[i][j]=dp[i−1][j]+grid[i][j]dp[i][j] = dp[i - 1][j] + grid[i][j]dp[i][j]=dp[i−1][j]+grid[i][j]

    • 第一列：dp[i][j]=dp[i][j−1]+grid[i][j]dp[i][j] = dp[i][j - 1] + grid[i][j]dp[i][j]=dp[i][j−1]+grid[i][j]

    • 其他：dp[i][j]=min(dp[i][j−1],dp[i−1][j])+grid[i][j]dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]dp[i][j]=min(dp[i][j−1],dp[i−1][j])+grid[i][j]

和最小下降路径不同，在这里不限制dp[i][j]dp[i][j]dp[i][j]的来源范围，所以dp数组的最后一个值就可以取到结果的最小值，返回dp数组最后一个元素即可。

代码

class Solution:
    def minPathSum(self, grid):
        '''
        dp[i][j]表示走到grid[i][j]位置的最小路径和。
        '''
        m, n = len(grid), len(grid[0])
        dp = [[0] * (n) for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, n):
            dp[0][i] = dp[0][i - 1] + grid[0][i]
        for j in range(1, m):
            dp[j][0] = dp[j - 1][0] + grid[j][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
        return dp[-1][-1]

该算法的时间复杂度为 O(mn)O(mn)O(mn)，因为算法需要遍历整个网格，对于每个网格点，需要进行一次常数时间的更新操作。空间复杂度也为 O(mn)O(mn)O(mn)，因为需要创建一个 m×nm\times nm×n 的二维数组来存储中间结果。

62. 不同路径

62. 不同路径

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

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

问总共有多少条不同的路径？

 

示例 1：

矩阵中的二维动态规划🐾

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

示例 2：

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

示例 3：

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

示例 4：

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

 

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

分析

这个和上一题没什么太大区别，唯一一点区别就是从计算路径和变成计算路径数量。

第一行只能从左边过来，就一条路径；第一列同理，只能从上边下来，就一条路径。其他的格子就是可以从左边，也可以从上边，所以到该格子的路径就是左边和上边格子的路径数加起来。

  • 递推公式：

    • 第一行：dp[i][j]=1dp[i][j] = 1dp[i][j]=1

    • 第一列：dp[i][j]=1dp[i][j] = 1dp[i][j]=1

    • 其他：dp[i][j]=dp[i][j−1]+dp[i−1][j]dp[i][j] = dp[i][j-1] + dp[i-1][j]dp[i][j]=dp[i][j−1]+dp[i−1][j]

注意一点，dp[0][0]代表啥？如果终点就在[0][0]的时候，你从[0][0]出发有几条路径。默认是1条。

起初我初始化为0，我想的[0][0]到[0][0]不用走，结果人有个测试样例要求是默认一条路径。

代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        '''
        dp[i][j]：从00-->ij的路径路径数量
        dp[0][0] = 1   --->  测试样例有个
        dp[i][0] = 1
        dp[0][j] = 1
        '''
        dp = [[1]*n for _ in range(m)]

        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[-1][-1]

该算法的时间复杂度为 O(mn)O(mn)O(mn)，因为算法需要遍历整个网格，对于每个网格点，需要进行一次常数时间的更新操作。空间复杂度也为 O(mn)O(mn)O(mn)，因为需要创建一个 m×nm\times nm×n 的二维数组来存储中间结果。

由于每个网格点的值只依赖于其左侧和上侧网格点的值，因此在实际实现中，可以将空间复杂度优化为 O(n)O(n)O(n) 或者 O(m)O(m)O(m)。

63. 不同路径 II

63. 不同路径 II

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

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

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

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

 

示例 1：

矩阵中的二维动态规划🐾

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

示例 2：

矩阵中的二维动态规划🐾

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

 

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

分析

和上一题的区别就在于这里多了个障碍。

注意这里初始化dp[0][0] = 0。

dp[0][0]代表啥？如果终点就在obstacleGrid[0][0]的时候，你从[0][0]出发有几条路径。起初我和上一题一样设置的是1，但是人这题有障碍啊，所以你初始化时候要初始为0，然后判断有无障碍再做决定要不要把这个点路径改为1。

代码

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid) -> int:
        '''
        dp[i][j]：从00-->ij的路径路径数量
        dp[0][0] = 0   --->  测试样例要求
        如果没障碍
        dp[i][0] = 1
        dp[0][j] = 1
        dp[i][j] = dp[i-1][j]+dp[i][j-1]
        如果遇到障碍，之后的直接跳过，无法到达。
        '''
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            dp[i][0] = 1
        for j in range(n):
            if obstacleGrid[0][j] == 1:
                break
            dp[0][j] = 1
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue    # 注意这里不是break了，之后的格子还要检查，因为有来自两个方向的路径
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[-1][-1]

假设网格的大小为 m×nm\times nm×n，则该算法的时间复杂度为 O(mn)O(mn)O(mn)，因为算法需要遍历整个网格，对于每个网格点，需要进行一次常数时间的更新操作。空间复杂度也为 O(mn)O(mn)O(mn)，因为需要创建一个 m×nm\times nm×n 的二维数组来存储中间结果。

矩阵中的面积

221. 最大正方形

221. 最大正方形 - 力扣（Leetcode）

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

 

示例 1：

矩阵中的二维动态规划🐾

输入： matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出： 4

示例 2：

输入： matrix = [["0","1"],["1","0"]]
输出： 1

示例 3：

输入： matrix = [["0"]]
输出： 0

 

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] 为 '0' 或 '1'

分析

这里dp数组含义比较憋屈，这里是表示ij为右下角的正方形的边长。能想到这一点就可以做这一题了。

代码

class Solution:
    def maximalSquare(self, matrix) -> int:
        '''
        dp数组表示以ij为右下角的正方形的边长
        '''
        m = len(matrix)
        n = len(matrix[0])
        length = 0
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    dp[i][j] = int(matrix[i][j])
                elif matrix[i][j] == '1':
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                length = max(length, dp[i][j])
        return length ** 2

使用动态规划思想，dp[i][j] 表示以 i,j 为右下角的正方形的边长。初始值为 matrix[i][j] 是否为 1。

然后遍历矩阵中的每一个元素，如果 matrix[i][j] 为 1，则 dp[i][j] 等于其上方、左方、左上方三个位置的 dp 值的最小值加 1。这里的三个位置表示以当前位置为右下角的正方形的三个边。

遍历完整个矩阵后，记录 dp 中的最大值，然后返回该值的平方，即为最大正方形的面积。

时间复杂度为 O(mn)O(mn)O(mn)，空间复杂度为 O(mn)O(mn)O(mn)。

85. 最大矩形

85. 最大矩形 - 力扣（Leetcode）

764. 最大加号标志

764. 最大加号标志 - 力扣（Leetcode）

转载自:https://juejin.cn/post/7238978524031189051
评论
请登录