计算GPA

寻找临界楼层

编辑距离

<pre><code># 创建一个二维数组，L[i][j]代表从A的前i位到B的前j位，需要多少步 L = [[0] * (len(B) + 1) for i in range(len(A) + 1)] # B的长度为0时，需要i步 for i in range(len(A) + 1): L[i][0] = i # A的长度为0时，需要j步 for j in range(len(B) + 1): L[0][j] = j # L[i][j]可以这样计算，取以下三种情况的最小值： # 1） 由L[i][j-1]的结果插入一个字符，即增加一个步骤，得到L[i][j]; # 2） 由L[i-1][j]的步骤加1，删掉第i位； # 3） 由L[i-1][j-1]得到，如果下一位相等，则不增加步骤，否则加一个步骤 for j in range(1, len(B) + 1): for i in range(1, len(A) + 1): if A[i - 1] == B[j - 1]: L[i][j] = min(L[i - 1][j - 1], L[i - 1][j] + 1, L[i][j - 1] + 1) else: L[i][j] = min(L[i - 1][j - 1] + 1, L[i - 1][j] + 1, L[i][j - 1] + 1) print(L[-1][-1])</code></pre>

动态规划

<a href="http://www.gznb.xyz/posts/pythonTip-99-编辑距离/">题解： http://www.gznb.xyz/posts/pythonTip-99-编辑距离/</a>

构造 L[i,j] &nbsp;意思就是A的前i位，B的前j位，都匹配好了，需要多少步1、A如果0位，B有多少位，就需要多少步2、否则的话 &nbsp;A有i位，B有j位，从哪里来呢，可以是（i-1，j）插一个字符，（i,j-1）插个字符，或者（i-1，j-1）后面一位改掉，这些都要加一步，唯独（i-1，j-1）后面A,B 要比较的一位相同的时候，就=（i-1，j-1）的步数 L=[[0 for i in range(len(B)+1)]for j in range(len(A)+1)] for i in range(len(A)+1): &nbsp; &nbsp; for j in range(len(B)+1): &nbsp; &nbsp; &nbsp; &nbsp; if i==0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]=j &nbsp; &nbsp; &nbsp; &nbsp; elif j==0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]=i &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if A[i-1]==B[j-1]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a=L[i-1][j-1] &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; a=L[i-1][j-1]+1 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; L[i][j]=min(a,L[i][j-1]+1,L[i-1][j]+1) print L[-1][-1]

原来这个叫dp

l1=len(A) l2=len(B) dp=[[0 for i in range(0,l2+2)] for j in range(0,l1+2)] for i in range(0,l1+1):dp[i][0]=i for i in range(0,l2+1):dp[0][i]=i dp[0][0]=0; for i in range(1,l1+1): &nbsp; &nbsp; for j in range(1,l2+1): &nbsp; &nbsp; &nbsp; &nbsp; if A[i-1]==B[j-1]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[i][j]=dp[i-1][j-1] &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[i][j]=dp[i-1][j-1]+1 &nbsp; &nbsp; &nbsp; &nbsp; dp[i][j]=min(dp[i-1][j]+1,dp[i][j]) &nbsp; &nbsp; &nbsp; &nbsp; dp[i][j]=min(dp[i][j-1]+1,dp[i][j]) print(dp[l1][l2])

这个题目使用二维的动态规划可以解决, 一开始思考是使用一维的,发现没有办法表示f(n)与f(n-1)之间的关系,关系太弱了, f(n)表示使用n个源字符进行操作得到目标字符的操作步数；所以就增加一维信息,我们使用f(i,j)表示成功使用了i个源字符进行操作得到了目标字符的步数,比如f(5,3)就是表示使用5个字符通过f(5,3)步操作成功匹配了目标字符串的3个字符(无论哪三个都可以)；因为一共有三种操作,所以其动态规划为f(i,j) = min(f(i-1,j) + 1, f(i,j-1) + 1, f(i-1, j-1) + (A[i-1] == B[j-1]))也就是当前使用i个字符去成配对j个目标字符的步数,是使用i-1个字符成功配对i个字符的情况下加1(也就是删除一个字符,多出来的是多余的,已经成功配对了j个了),使用i个字符去成功配对j-1个字符的情况下去增加一个字符(增加的字符就是源字符里面目前对于目标字符来说少的那个),使用i-1个字符去配对j-1个字符的情况下,去判断彼此两个字符的当前位置是否是一样的,不一样的话,就进行修改,加1次操作；代码如下:<pre class="prettyprint lang-py linenums">def dp(A, B):
	src_size = len(A)
	tgt_size = len(B)
	steps = [[0 for i in range(tgt_size + 1)] for j in range(src_size + 1)]
	for i in range(src_size+1):
		for j in range(tgt_size+1):
			if i == 0 or j == 0:
				steps[i][j] = max(i,j)
			else:
				steps[i][j] = min(steps[i-1][j] + 1, steps[i][j-1] +1)
				temp = 0
				if A[i-1] != B[j-1]: #这里的位置要区分好,判断steps[i][j]的最后一个字符是i-1和j-1,因为字符是从0计数的
					temp = 1
				steps[i][j] = min(steps[i-1][j-1] + temp, steps[i][j])
	return steps[src_size][tgt_size] 

A=&quot;fxpimu&quot;
B=&quot;xwrs&quot;
print dp(A, B)</pre>

动态规化

dp[i][j] = min(dp[i-1]+1,dp[i][j-1]+1,dp[i-1][j-1]+(a[i]==b[j])<pre style="padding: 9.5px; font-family: Monaco, Menlo, Consolas, 'Courier New', monospace; font-size: 13px; color: rgb(51, 51, 51); border-top-left-radius: 4px; border-top-right-radius: 4px; border-bottom-right-radius: 4px; border-bottom-left-radius: 4px; margin-top: 0px; margin-bottom: 10px; line-height: 20px; word-break: break-all; word-wrap: break-word; white-space: pre-wrap; background-color: rgb(245, 245, 245); border: 1px solid rgba(0, 0, 0, 0.14902);">#A = raw_input()
#B = raw_input()
l1 = len(A)
l2 = len(B)
dp = [[0]*(l2+1) for i in range(l1+1)]

for i in range(0, l1+1):
 for j in range(0, l2+1):
 if i == 0 or j == 0:
 dp[i][j] = max(i, j)
 else:
 dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1)
 tag = 0
 if A[i-1] != B[j-1]:
 tag = 1
 dp[i][j] = min(dp[i][j], dp[i-1][j-1] + tag)
print dp[l1][l2]
</pre><div> </div>

网上有现成的代码 lens = len(A)lent = len(B) dp = [[0]*(lent+1) for i in range(lens+1)] for i in range(0, lens+1): &nbsp;&nbsp;&nbsp; for j in range(0, lent+1): &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if i == 0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; dp[i][j]=j &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; elif j==0: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; dp[i][j]=i &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; extra = 0 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if A[i-1] != B[j-1]: extra = 1 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; dp[i][j] =min( min(dp[i-1][j]+1,dp[i][j-1]+1), dp[i-1][j-1]+extra)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; print dp[lens][lent]

感谢楼主<img alt="微笑" src="http://2.pythontip.sinaapp.com/static/xheditor/xheditor_emot/default/smile.gif" />

举个例子 cafe -&gt; coffee[# #&nbsp; c, o, f,&nbsp; f, e, e] [# 0, 1, 2, 3, 4, 5, 6] [c 1, 0, 1, 2, 3, 4, 5] [a 2, 1, 1, 2, 3, 4, 5] [f 3, 2, 2, 1, 2, 3, 4] [e 4, 3, 3, 2, 2, 2, 3]

&nbsp; 其实很好理解，就是求一个矩阵，源字符串为行，目标字符串为列，矩阵大小均为字符串长度+1举证的最后一行最后一列那个数就是你要求的值。这个状态正好是源目标字符串到目标字符串的编辑距离，因为这个矩阵的每一个元素都是不同状态下的编辑距离，目标状态的前一状态涉及到左边、左上、和正上方这3个状态，所以根据初始状态把矩阵元素都算出来就可以了。

第99题：编辑距离

计算两点间的距离

特殊的倍数

进制转换

输出字典key