[数据结构与算法]200道大数据面试常考Leetcode算法题--动态规划进阶(与矩阵相关)篇（python带代码解析）

往期内容在这里：

往期01-05

往期06-10

往期11-15

往期16-20

数组篇01

数组篇02

数组篇03

数组篇04

动态规划篇

大家好，继续为大家推荐200道大数据面试常考Leetcode算法题，这期为--动态规划进阶(与矩阵相关)篇，附带解析，都是从Leetcode官网总结大神们的解法（在这里感谢大神的帮助，我只是个搬运工！）这篇更新4篇，艾瑞巴迪和我一起刷起来！！

200道大数据面试常考Leetcode算法题（动态规划进阶(与矩阵相关)篇）62-不同路径

leetcode原题：

题解为：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 定义一维空间，其大小为 n，值全是1
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                # i行第j列位置的路径数量 = 
                # 第i - 1行第j列位置的路径数量（上方值） + 第i行第j - 1列位置的路径数量（左边）
                dp[j] = dp[j] + dp[j - 1]
        # 返回最后一个的结果
        return dp[-1]

200道大数据面试常考Leetcode算法题（动态规划进阶(与矩阵相关)篇）63-不同路径Ⅱ

Leetcode原题：

?题解为：

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        width = len(obstacleGrid[0])
        dp = [0 for i in range(width)] 
        dp[0] = 1
        # 自低向上循环
        for row in obstacleGrid:
            for j in range(width):
                # 左边的格子如果没有障碍物就是1，如果有障碍物则是0
                if row[j] == 1:
                    dp[j] = 0
                # 当前格子走法 = 右边格子走法 + 下方格子走法
                elif j > 0:
                    dp[j] += dp[j - 1]
        return dp[width - 1]        
        

200道大数据面试常考Leetcode算法题（动态规划进阶(与矩阵相关)篇）64-最小路径和

Leetcode原题：

题解为：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # i为数组的行
        for i in range(len(grid)):
            # j为数组的列
            for j in range(len(grid[0])):
                # 判断当位于第一行
                if (i == 0 and j != 0):
                    # 所有的dp[i - 1][j] 都在第一行上边，出了数组上边界
                    grid[i][j] += grid[i][j - 1]
                # 判断当位于第一列
                elif (i != 0 and j == 0):
                    # 所有的 dp[i][j - 1] 都在第一列左边，出了数组左边界
                    grid[i][j] += grid[i - 1][j]
                # 当位于第一行第一列（i == 0 and j == 0）
                elif (i == 0 and j == 0):
                    continue
                # 位于数组里面某一位置
                else:
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        # 遍历完全部行和列之后，返回最后的值 dp[-1][-1]
        return grid[-1][-1]

200道大数据面试常考Leetcode算法题（动态规划进阶(与矩阵相关)篇）221-最大正方形

Leetcode原题为：

题解为：?

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # 定义边长
        r = 0
        row = len(matrix)#行
        col = len(matrix[0])#列
        for i in range(row):
            for j in range(col):
                matrix[i][j] = int(matrix[i][j])#转为数字好判断点
                if i and j and matrix[i][j]:
                    #转移方程，依赖于左边，上面，左上面的最大边数，选择最小的一个边
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i][j-1], matrix[i-1][j-1]) + 1
                # 找到最大的边长
                r = max(r, matrix[i][j])
        #返回面积
        return r * r

好啦，这期的分享到这里结束啦！我们下期（动态规划在进阶(序列类动态规划问题)篇）再见！