有一个需求，在一堆的字符串中，找出所有相似的字符串对。其中数据有这样的特点：大部分差异很大，一些字符串相等，另一些有个别字符不一样。后找到了一个算法：最小编辑算法。原理就不说了，需要的去百度一下。
当然，这个Edit distance算法的效率还是可以的，O(n^2)，但我其实只需要判断是否相似（最终代价小于某个值minV），而不是差异有多大，因此想到优化方案：如果当前dp过程中，发现到终点的必经之路的代价最小值大于minV，则判断不相似，直接返回false。因此，需要找到必经之路，和计算最小值。
在经典的ED算法中，结构很简单，一个嵌套的循环和一个状态转移方程。
```java
for(int i=0;i<len1;i++)
for(int j=0;j<len2;j++)
a[i][j]=min(a[i-1][j]+1,a[i][j-1]+1,a[i-1][j-1]+(s1[i]==s2[j]?0:1));
```
大致下图的顺序
以获得最终代码为目标，这样差不多效率到了极致了。
但我不需要这么详细的结果。
回到之前的需要：必经之路和最小代价
显然，要到达红色位置，必然经过一个或多个黑色位置。
那么如果红色的代价至少不小于黑色代价的最小值。这不是显然的嘛...
当然，我们不能到终点了才判断，那就没意义了。往前扩展，可以得到下图
但是，这里黑色区域的最小代价是0，而已传统的ED算法，至少得算minV行才可能得到大于minV的代价。于是乎，修改一下遍历顺序：
这样，能很快得到第一个大于minV的必经之路最小代价。
需要计算两行的最小代价（黄线）如果这些最小代价均大于minV，则最终代价一定大于minV，判定为不相似。
有同学要问了，只计算黄线区域，万一边上的代价小于或等于minV呢？
能看懂箭头吧：蓝色>=minV，否则边上的黑色(黄线)就不能保证>=minV+1，与黄线最小值大于minV不符。
效率比较：
造数据：生成500条随机数据f(len,max)（执行500*499/2次ED算法
）
len是随机字符串长度，max是每个字符的可能（或者说每个字符是1-minV中的一个）
如f(5,3)可能是31213
判断相似的最小代价minV
附上我的测试结果：（在公司服务器上测的，所有每次结果都不一样）
f(50,2) minV=5 标准ED耗时 2.7s 优化ED耗时1.2s 相似对 0
f(50,2) minV=10 标准ED耗时 2.1s 优化ED耗时2.5s 相似对 112
f(50,10) minV=10 标准ED耗时 2.3s 优化ED耗时0.6s 相似对 0
f(50,10) minV=10 标准ED耗时 2.1s 优化ED耗时0.9s 相似对 0
f(50,10) minV=50 标准ED耗时 2.1s 优化ED耗时3.1s 相似对 124750
结果符合预期：如果minV太大，优化ED更耗时，因为运行效率的系数更大（似乎差距不算太大）
在数据差异很大，并且minV远小于len时，效率有极大改善。
不错，很符合我的需求。bingo
（代码在公司服务器上，没法复制出来，就不贴出来了）
