本文讲述了python基础编程100例：第71期-基础算法：动态规划 01矩阵！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

第71期-基础算法：动态规划 01矩阵

1 问题描述

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

示例 1:

输入: mat = [[0,0,0],[0,1,0],[0,0,0]]

输出: [[0,0,0],[0,1,0],[0,0,0]]

示例 2:

输入: mat = [[0,0,0],[0,1,0],[1,1,1]]

输出: [[0,0,0],[0,1,0],[1,2,1]]

初始代码

from typing import List

class Solution:

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:

        #在此之间填写代码

print(Solution().updateMatrix([[0,0,0],[0,1,0],[0,0,0]]))

print(Solution().updateMatrix([[0,0,0],[0,1,0],[1,1,1]]))

2 解题思路

标签：动态规划

首先把每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散

扩散过程中可以把所有的1变成-1，这样不会担心距离一与原本的一弄混

3 解题方法

from typing import List

class Solution:

    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:

        queue=[]

        a,b=len(mat),len(mat[0])

        for i in range(a):

            for j in range(b):

                if mat[i][j]==1:mat[i][j]=-1

                if mat[i][j]==0:queue.append((i,j))

        x=0

        while x<len(queue):

            cur = queue[x]

            for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:

                if 0<=cur[0]+i<a and 0<=cur[1]+j<b and mat[cur[0]+i][cur[1]+j]==-1:

                    mat[cur[0]+i][cur[1]+j]=mat[cur[0]][cur[1]]+1

                    queue.append((cur[0]+i,cur[1]+j))

            x+=1

        return mat

print(Solution().updateMatrix([[0,0,0],[0,1,0],[0,0,0]]))

print(Solution().updateMatrix([[0,0,0],[0,1,0],[1,1,1]]))

第1-3，21-22行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑

第4行： 定义列表queue用于存放需要遍历的节点

第5行： 定义变量a、b分别用于存放矩阵的长和宽

第6-7行： 使用for循环遍历矩阵中的每一个值

第8行： 将矩阵中的1全部标记为-1

第9行： 将举证中的0行列索引全部加到列表queue中

第10行： 定义变量x=0用于矩阵索引

第11行： 当未遍历完矩阵中的所有元素时，继续循环

第12行： 定义变量cur用于存放第一个需要扩散变量的位置

第13行： for循环用于遍历该点的四个扩散方向

第14行： 判断扩散方向的点是否在矩阵内部且数值为-1时（也就是还未扩散）

第15行： 改变该点的数值为扩散源头的数值加一，表示距离加一

第16行： 在queue列表中加入该点，用于以后该点扩散

第17行： 索引值加一，进行下一个点的扩散

第18行： 当全部遍历完成之后，返回遍历之后的列表

代码运行结果为：

算法讲解

这里用到了基础算法：动态规划，简单讲解下这个算法：

动态规划

动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

性质

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。

2. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

3. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

性质

1. 划分：按照问题的特征，把问题分为若干阶段。注意：划分后的阶段一定是有序的或者可排序的

2. 确定状态和状态变量：将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性

3. 确定决策并写出状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程

4. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。