单词变身游戏（动态规划算法应用）

这道题运用的就是动态规划的思想。

动态规划简单来说就是我们利用历史数据去推出新的数据来，减少我们的计算量。

动态规划的题可以分为三步：

• 第一步我们要确定我们数组里的每个元素代表的是什么含义
• 第二步，我们要确定初始值该怎么设立？
• 第三步，我们要确定如何用历史数据去推出新的数据
• 我们以这道题为例来看。首先，我们要确定我们说的这个数组是什么含义？我这里的表是b[i][j]代表的，第一个字符串的前i个字符如果转换成第二个字符串前j个字符最少需要多少步.
• 第二步要设定初始值，根据推理，我们可以得知，如果是b[i][0]这种情况下需要转换i步，因为只需要做删除 *** 作，就是有几个字符，我们就要删除几个嘛。同理，b[0][j]它的初值是b[0][j]=j
• 最后一步也是最麻烦的一步，我们要找到历史数据和新数据之间的关系，通过题意，我们可以得知他能做的 *** 作分别有三个插入，删除跟替换。但是不是做这个 *** 作？我们要去判断第一个字符串的，第i个字符和第二个字符串的第j个字符是否相同？如果相同的话，我们就不用做任何 *** 作,直接让b[i][j]=b[i-1][j-1]，判断下一轮。
• 否则我们就要做上述的三个 *** 作，分别来看。
• 首先是替换，替换的话，证明两个字符串的长度是一致的，所以我们直接去继承dp[i-1][j-1]的最小次数再加一就可以，加一就是替换这一次.
• 其次是删除，由于我们删除完一个字符以后,第一个字符串长度变成了i-1，所以我们的数量就是dp[i-1][j]，再加上一.
• 最后是插入原理同上，所以我们是dp[i][j-1]+1。
• 所以我们就推出了公式

  if(a[0][i-1]==a[1][j-1]):  
            dp[i][j]=dp[i-1][j-1]  
        else:  
            dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1

  2.扩展知识：np.zeros() 的作用返回来一个给定形状和类型的用0填充的数组zeros(shape, dtype=float, order='C')，shape：表示形状dtype:数据类型，可选参数，默认numpy.float64，order:可选参数，c代表行优先；F代表列优先。

• 代码如下：

• import numpy as n  
  dp=n.zeros((1000,1000),dtype=int)#这一步是创建一个int类型二维的dp数组，1000行1000列。  
  a=input()  
  a=a.split(",")#以逗号为分隔符拆分字符串  
  for i in range(len(a[0])+1):#设定初始值`b[i][0]`这种情况下需要转换`i`步因为只需要做删除 *** 作，就是有几个字符，我们就要删除几个嘛。  
     dp[i][0]=i  
  for i in range(len(a[1])+1):#同理，`b[0][j]`它的初值是`b[0][j]=j`  
     dp[0][i]=i  
  for i in range(1,len(a[0])):  
     for j in range(1,len(a[1])):  
         if(a[0][i-1]==a[1][j-1]):#第一个字符串的第i个字符和第二个字符串的第j个字符是相同的话  
             dp[i][j]=dp[i-1][j-1]#直接让`b[i][j]=b[i-1][j-1]`，判断下一轮。  
         else:  
             dp[i][j]=min(dp[i-1][j-1]+1,dp[i-1][j]+1,dp[i][j-1]+1)  
  #他能做的 *** 作分别有三个插入，删除跟替换取最小值  
  print(dp[len(a[0])-1][len(a[1])-1])