Leetcode刷题笔记——多维动态规划篇

第一题:最小路径和

Leetcode64：最小路径和：中等题 （详情点击链接见原题）

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

python代码解法

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])  # m 行 n 列
        dp_matrix = [[0] * n for _ in range(m)]
        dp_matrix[0][0] = grid[0][0]
        for i in range(1, n):  # dp数组初始化
            dp_matrix[0][i] = dp_matrix[0][i - 1] + grid[0][i]
        for j in range(1, m):
            dp_matrix[j][0] = dp_matrix[j - 1][0] + grid[j][0]
        
        for x in range(1, m):
            for y in range(1, n):
                dp_matrix[x][y] = min(dp_matrix[x][y - 1] + grid[x][y], dp_matrix[x - 1][y] + grid[x][y])
        # print(dp_matrix)
        return dp_matrix[m - 1][n - 1]

第二题:三角形最小路径和

Leetcode120. 三角形最小路径和：中等题 （详情点击链接见原题）

给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

python代码解法

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = [[0 for _ in range(len(tri))] for tri in triangle]
        dp[0][0] = triangle[0][0]
        for i in range(1, len(triangle)):
            for j in range(0, len(triangle[i])):
                if 0 < j < len(triangle[i]) - 1:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j] + triangle[i][j]
                else:
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
        return min(dp[len(triangle) - 1])

第三题:不同路径

Leetcode62. 不同路径：中等题 （详情点击链接见原题）

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

解题思路
机器人从(0 , 0) 位置出发，到 (m - 1, n - 1) 终点

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

2.确定递推公式
dp[i][j] 只能有两个方向来推导出来，即 dp[i - 1][j] 和 dp[i][j - 1]，dp[i - 1][j] 表示从 (0, 0) 的位置到 (i - 1, j) 有几条路径

3.dp数组如何初始化
dp[i][0] 和 dp[0][j] 一定都是1，因为从 (0, 0) 的位置到 (i, 0)和 (0, j) 的路径只有一条

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

5.举例推导 dp 数组
在这里插入图片描述

python代码解法

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]

        # dp 数组初始化
        for row in range(m):
            dp[row][0] = 1
        for col in range(1, n):
            dp[0][col] = 1

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

第四题:不同路径 II

Leetcode63. 不同路径 II：中等题 （详情点击链接见原题）

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

python代码解法

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]  # dp 数组初始化
        if obstacleGrid[0][0] == 1:
            return 0
        for row in range(m):
            if obstacleGrid[row][0] != 1:
                dp[row][0] = 1
            else:
                break
        for col in range(1, n):
            if obstacleGrid[0][col] != 1:
                dp[0][col] = 1
            else:
                break
        for row in range(1, m):
            for col in range(1, n):
                if obstacleGrid[row][col] != 1:
                    dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
                else:
                    continue
        return dp[m - 1][n - 1]

第五题

Leetcode221. 最大正方形：中等题 （详情点击链接见原题）

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

1. 确定 dp 数组（dp table）以及下标的含义
dp[i][j] : 多补充一行全 0、多一列全 0后 dp[i][j] 的含义为以 matrix[i[j] 为右下角的正方形的最大边长

在这里插入图片描述

2. 确定递推公式
dp[r][c] = min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1
翻译成中文为若某格子的值为 1，则以此为右下角的正方形的最大边长为：上面的正方形，左边的正方形，左上的正方形中边长最小的那个，再加上此格

python代码解法

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or len(matrix) < 1 or len(matrix[0]) < 1:
            return 0
        row, col = len(matrix), len(matrix[0])
        maxSide = 0
        dp = [[0 for _ in range(col + 1)] for _ in range(row + 1)]
        for r in range(1, row + 1):
            for c in range(1, col + 1):
                if matrix[r - 1][c - 1] == '1':
                    dp[r][c] = min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]) + 1
                    maxSide = max(maxSide, dp[r][c])
        return maxSide * maxSide