编辑距离
典型的动态规划题目，初看无从下手，但按照动态规划套路一步步来也不是很难。
动态规划步骤：
1、确定初始边界条件。
2、确定状态转移方程。
3、写代码。
先解释一下什么是初始边界条件
边界条件
动态规划一般是多变量之间的相互作用，正常人脑（反正当初我刚刚接触动态规划是头疼+心态爆炸）难以一下子考虑
f
（
x
1
,
x
2
.
.
.
.
x
n
）
f（x_1,x_2….x_n）
f
（
x
1
,
x
2
.
.
.
.
x
n
）
中n个变量，然后一口报出来
x
1
,
x
2
.
.
.
.
x
n
x_1,x_2….x_n
x
1
,
x
2
.
.
.
.
x
n
分别取什么值使得
f
f
f
最大或最小。所以我们一般先考虑
f
(
x
1
,
0
,
0….0
)
、
f
(
0
,
x
2
,
0….0
)
.
.
.
.
.
.
.
f
(
0
,
0
,
0….
x
n
)
f(x_1,0,0….0)、f(0,x_2,0….0)…….f(0,0,0….x_n)
f
(
x
1
,
0
,
0
.
.
.
.
0
)
、
f
(
0
,
x
2
,
0
.
.
.
.
0
)
.
.
.
.
.
.
.
f
(
0
,
0
,
0
.
.
.
.
x
n
)
,也就是数学中常说的控制变量法。
状态转移方程
这个是所有动态规划题目中最重要的一环，笔者尝试找到一个固定的套路可以解决大部分动态规划问题，发现暂时还做不到，可能是题目做少的原因。不得不说，动态规划是真的难！！！
本题的状态转移方程为：
写代码
import numpy as np
b="apple"
a="rad"
lena=len(a)
lenb=len(b)
dis=np.zeros((lena+1,lenb+1))
path=nd_test = np.full(shape=((lena+1,lenb+1)),fill_value='a5i')
#初始化有一个字符串长度为0的情况
for i in range(lena+1):
for j in range(lenb+1):
if(i==0):
dis[i][j]=j
path[i][j]="→"
elif(j==0):
dis[i][j]=i
path[i][j]="↓"
elif (a[i-1]!=b[j-1]):
dis[i][j]=min(dis[i-1][j]+1,dis[i][j-1]+1,dis[i-1][j-1]+1)
if dis[i][j]==dis[i-1][j]+1:
path[i][j]="↓"
elif dis[i][j]==dis[i][j-1]+1:
path[i][j]="→"
else:
path[i][j]="↓→"
else:
dis[i][j]=dis[i-1][j-1]
path[i][j]="↓.→"
print("距离矩阵为：")
print(dis)
print("来的时候的路径")
print(path)
for i in range(lena+1):
for j in range(lenb+1):
if(path[i][j]=="→"):
path[i][j]="←"
elif(path[i][j]=="↓"):
path[i][j]="↑"
elif (path[i][j]=="↓.→"):
path[i][j]="←.↑"
else:
path[i][j]="←↑"
print("回去的路径")
print(path)
运行结果：
