# 第71期-基础算法：动态规划 01矩阵
Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。
# 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
3
4
5
6
7
# 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]]))
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
第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. 边界条件：状态转移方程是一个递推式，因此需要找到递推终止的条件
# 4 视频解析
高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码 