寫這篇文章剖笙，
一卵洗、DiffUtil 對比列表item 數(shù)據(jù)，git 文件對比都用到了這個算法。
二过蹂、發(fā)現(xiàn)國內(nèi)的博客十绑，帖子，對這個算法的描述很少很少酷勺，算法本身又難以理解本橙。
三、上篇DiffUtil 源碼分析時(shí)遇到了這個算法脆诉，我覺得程序員不能怕算法甚亭，要跟算法死磕到底，要往下挖源碼击胜。
書讀百遍其義自現(xiàn)亏狰，閱讀算法代碼也是如此。
對比原則和圖畫結(jié)合
兩個字符串,a = "ACBA" b = "CBA"對比這兩個字符的差異偶摔，有什么發(fā)現(xiàn)暇唾？
你會脫口而出 ：
a 比 b 最前面多了一個"A"
為什么不是:
第一位，A≠C,第二位辰斋，C≠B,第三位策州，B≠A,第四位，b少了一位
由此得到我們對比的原則（我總結(jié)的）：
- 計(jì)算最大重合部分（"CBA"）宫仗，改變字符最小的原則抽活。
用圖片表示，畫上斜線的格子就是重合的部分（"CBA"）锰什。（注意這張圖片下硕，這個算法是用表格的方式理解的）
我們最開始的描述： 第一位多了一個"A"，其余不變汁胆，是改變最小的
圖表的描述就是：x 方向(向右)一步梭姓，其余斜線，是橫縱走得最少的嫩码。
- 向右一步=增加了 "A"誉尖，改變最小=橫縱走得最少
看圖：
新數(shù)據(jù)a = "AB" 比上 b= "BB"
有兩條最短路徑，向右一步铸题，向下一步或者向下一步铡恕，向右一步。
我們選擇向右一步向下一步的丢间，圖表的方式是：向右一步再向下一步探熔，其余斜線。我們的描述是：新數(shù)據(jù)a相對于舊數(shù)據(jù)b烘挫，第一位增加了a中的A诀艰，減去了b中的B，其余不變。
- 向下=減去
上面能做到圖畫其垄，和邏輯結(jié)合了苛蒲，請看下面這樣一個問題：
a = "ABCABBA"
b ="CBABAC"
a的長度7，b的長度等于6
它的最小改變的描述是如何绿满？
這個問題可以改成臂外，從 起點(diǎn) （0，0）到 終點(diǎn)（7喇颁，6）的最短橫縱路徑是怎么走寄月？
一目了然，當(dāng)黃色路徑達(dá)只要五步就到達(dá)的時(shí)候无牵，其他路徑還沒有到達(dá)。
邁爾斯的 diff 算法就是比較快速求出這樣一條路徑的算法厂抖。
提出概念
（需要結(jié)合圖畫理解茎毁，這些概念的提出是為計(jì)算和表達(dá)方便，涉及數(shù)學(xué)忱辅，類似設(shè)個x ,設(shè)個y 的未知數(shù)）
snake :一步所走的路徑 為 snake七蜘，有所不同的是，snake 分為三個點(diǎn)墙懂，起點(diǎn)橡卤，中點(diǎn)，終點(diǎn)损搬，
一般走一步?jīng)]有遇到斜線碧库，中點(diǎn)就是終點(diǎn)， 遇到了的話巧勤，路徑就包含了斜線 ,終點(diǎn)坐標(biāo)計(jì)算也要包含斜線的坐標(biāo)嵌灰。k ： 定義x 軸向右增大，y軸 向下增大颅悉，定義 k = x-y沽瞭；
d ： 定義為步數(shù)。
看下圖：
2566000-f8f59baffd4eb418.png
黃色的線：k線 （注意這些線）
深藍(lán)色的線：snake
淺藍(lán)色的數(shù)字：d (步數(shù))
紅色的線：算法求出的問題的解（其實(shí)這個解有多個這只是求了其中一條）
怎么冒出來的這個k剩瓶？ 所有k相同的點(diǎn)組成了一條線驹溃，他們組成了對角線。并且對于k延曙，我們可以使用一個記錄的數(shù)組V豌鹤，用k作為該數(shù)組的index，x為value枝缔，這樣我們可以計(jì)算求得 y值
這個算法父問題的求解歸結(jié)為子問題的求解傍药。要知道d=5時(shí)所有k對應(yīng)的最優(yōu)坐標(biāo)，必須先要知道d=4時(shí)所有k對應(yīng)的最優(yōu)坐標(biāo)，要知道d=4時(shí)的答案拐辽，必須先求解d=3拣挪，以此類推。
思考：
如何使用最小d（步數(shù)） 到達(dá)終點(diǎn)（N俱诸，M）菠劝，可以得到外循環(huán)。
接下來我們想想如何到達(dá)point（x睁搭，y）赶诊？ 設(shè) k = x - y，那么能到達(dá)點(diǎn)（x园骆，y）的 只能從k-1 或者 k+1兩條對角線上到k上舔痪，步數(shù)的遞增，內(nèi)循環(huán)應(yīng)該是k 锌唾，內(nèi)層循環(huán)完畢的結(jié)果就是锄码，在步數(shù)為d，求得對角線k能到達(dá)的最遠(yuǎn)的x坐標(biāo)晌涕。每向下或向右一步滋捶，坐標(biāo)必然會從一條k線上移動到另外一條k線上，也就是說步數(shù)固定情況下余黎，k的改變重窟，我們可以求出相應(yīng)的移動方向從而確定路徑，內(nèi)循環(huán)就是k遞增惧财，找到最快一條到達(dá)終點(diǎn)（N,M）的路巡扇，目的就達(dá)成了
上偽代碼好好理解下：
偽碼分析
一般到這里就會很多的疑惑，很懵逼：
我們拆分下：
-
最外面這個循環(huán)
//d 是步數(shù)垮衷，N 是字符的長度6 霎迫，M 是字符長度7 , //縱然 d 一直右向，再向下帘靡，經(jīng)過斜線知给，也是大于不了N+M 的 for (int d = 0; d<= N +M ;d++){ ··· } 里面這層循環(huán)
- k = x-y ； 我們可以通過x 求y 描姚，v[]數(shù)組里面以k為index,存儲最優(yōu)坐標(biāo)的x值涩赢，取的時(shí)候只要知道k值，因?yàn)関[k] =x;通過有y =v[k]-k 就可以算出y轩勘；
k 結(jié)合圖形筒扒，我們從（0,0）開始，每次只增長一步绊寻，向下一步=>k-1花墩，向右一步=>k+1悬秉；
第一步：k的極限，k-1<= k <=k+1
第二步：k的極限冰蘑，k-2<= k <=k+2
第d步： k的極限和泌，k-d<= k <= k+d最短d步到達(dá)終點(diǎn)（x,y），假設(shè)途中經(jīng)過 一個 3個斜線祠肥，經(jīng)過橫線 i 個,經(jīng)過豎線 j 個
則x = i+3,y = j+3;終點(diǎn):（x武氓，y）=>（i+3，j+3）
假設(shè) d 是奇數(shù)仇箱，i+j 必然是奇數(shù)
由k = x-y = i +j +6;
得k 為奇數(shù)县恕，d 為奇數(shù)，k 只能為奇數(shù)剂桥，
所以內(nèi)循環(huán)時(shí) 忠烛，k +=2（看圖，這句話的意思是一個方格不能從對角線到對面的點(diǎn)权逗，不是向下美尸，就是向右）
// 每一步遞增
for (int d = 0; d<= N +M ;d++){
//在每一步下面的各個k的取值，k+=2 （見上面地三點(diǎn)）
for( int k = -d ;k <= d ;k +=2){
// 是否向下
//這里注意看圖上黃色斜線旬迹，起點(diǎn)k=0時(shí)；k= -1 是向下一步求类，當(dāng)k=-d 時(shí)必然向下 奔垦，k=d 必然向右，第一步d=1 ,k=-1向下尸疆，k = 1 向右椿猎。
//v[ ]數(shù)組保存了k上的 x ，看圖寿弱， 從第一步完成后犯眠，執(zhí)行第二步，d =2 ,k = - 2, 0 ,2三個數(shù)症革，
// k = -2 時(shí)筐咧，向下; k = 0 ，(這時(shí)右邊的k線 => v[k+1] =1(第一步記錄v[ ]為1)噪矛，左邊的k線 => v[k-1] =0(第一步結(jié)束時(shí)記錄為零)量蕊，
// 所以向下，k =2 , v[k+1] = 0(沒有保存) v[k-1] = 1（第一步保存為1）
// 這樣寫的好處艇挨，以k 為基準(zhǔn)進(jìn)行的移動残炮，不會出現(xiàn)重復(fù)的情況
bool down = ( k== - d || (k !=d && v[k-1] < v[ k+1] ));
···
//save end point
//保存對應(yīng)k 的x方向的值（這里的x向右0到7，y向下0到6 ）= 保存d步結(jié)束缩滨，對應(yīng)k值上的終點(diǎn)坐標(biāo)势就；
//終點(diǎn)坐標(biāo)(x,y)=> （x=v[k]泉瞻，y= v[k]-k）
v[k] = xEnd;
}
}
-
整個偽碼流程
//新建集合，用k值保存對應(yīng)的x v[ 1 ] = 0; //步數(shù)遞增 for (int d= 0; d <= N+M ;d++){ //每一步下面的各個k 的取值循環(huán)苞冯， for( int k = -d ; k <= d ; k+=2){ // 是否向下 bool down = ( k== - d || (k !=d && v[k-1] < v[ k+1] )); //得到上次移動的k,如果這次向下袖牙，上次的kPrev = k+1; int kPrev = down ? k+1 : k -1; //起點(diǎn)，因?yàn)槊看我苿颖４媸?k+2 ,所以如果這次的index全是奇數(shù)抱完，上一次就全是偶數(shù)贼陶，在一個數(shù)組里面不會進(jìn)行覆蓋 int xStart = v[kPrev] int yStart = xStart - v[kPrev] //中點(diǎn)钮追，之前說的坪稽，如果沒有遇到斜線，它是等于終點(diǎn)的 int xMid = down ? xStrat : xStart +1; int yMid = xMid - k峰档； //終點(diǎn)禁添，沒有遇到斜線的樣子 int xEnd = xMid; int yEnd = yMid; //斜線數(shù)量 int s= 0 //這就是遇到斜線撮胧，只有數(shù)據(jù)相等，才會是斜線老翘，然后芹啥，x,y 各加一 while(xEnd < N && yEnd <M && A[xEnd] ==B[yEnd]){ xEnd++; yEnd++; s++; } // 保存到數(shù)組 v[k] = xEnd; //到了最終點(diǎn)（N,M）,找到了最短步數(shù)的方案 if(xEnD >= N && yEnd > = M){ //跳出循環(huán) } } }
如果看了我注釋還是沒有懂，我推薦幾個網(wǎng)址：
外文的博客,加載有點(diǎn)慢
從DiffUtil到Myers'差分算法
Git是怎樣生成diff的：Myers算法
java實(shí)現(xiàn)
算法的論文
如果還沒有懂铺峭，結(jié)合圖案墓怀，多讀幾遍，注意他的每走一步其實(shí)就是k線上切換卫键。
