寫這篇文章，
一、DiffUtil 對比列表item 數據，git 文件對比都用到了這個算法。
二、發(fā)現(xiàn)國內的博客，帖子，對這個算法的描述很少很少，算法本身又難以理解。
三、上篇DiffUtil 源碼分析時遇到了這個算法，我覺得程序員不能怕算法，要跟算法死磕到底，要往下挖源碼。
書讀百遍其義自現(xiàn)，閱讀算法代碼也是如此。
對比原則和圖畫結合
兩個字符串,a = "ACBA" b = "CBA"對比這兩個字符的差異，有什么發(fā)現(xiàn)？
你會脫口而出 ：
a 比 b 最前面多了一個"A"
為什么不是:
第一位，A≠C,第二位，C≠B,第三位，B≠A,第四位，b少了一位
由此得到我們對比的原則（我總結的）：
- 計算最大重合部分（"CBA"），改變字符最小的原則。
用圖片表示，畫上斜線的格子就是重合的部分（"CBA"）。（注意這張圖片，這個算法是用表格的方式理解的）
我們最開始的描述： 第一位多了一個"A"，其余不變，是改變最小的
圖表的描述就是：x 方向(向右)一步，其余斜線，是橫縱走得最少的。
- 向右一步=增加了 "A"，改變最小=橫縱走得最少
看圖：
新數據a = "AB" 比上 b= "BB"
有兩條最短路徑，向右一步，向下一步或者向下一步，向右一步。
我們選擇向右一步向下一步的，圖表的方式是：向右一步再向下一步，其余斜線。我們的描述是：新數據a相對于舊數據b，第一位增加了a中的A，減去了b中的B，其余不變。
- 向下=減去
上面能做到圖畫，和邏輯結合了，請看下面這樣一個問題：
a = "ABCABBA"
b ="CBABAC"
a的長度7，b的長度等于6
它的最小改變的描述是如何？
這個問題可以改成，從 起點 （0，0）到 終點（7，6）的最短橫縱路徑是怎么走？
一目了然，當黃色路徑達只要五步就到達的時候，其他路徑還沒有到達。
邁爾斯的 diff 算法就是比較快速求出這樣一條路徑的算法。
提出概念
（需要結合圖畫理解，這些概念的提出是為計算和表達方便，涉及數學，類似設個x ,設個y 的未知數）
snake :一步所走的路徑 為 snake，有所不同的是，snake 分為三個點，起點，中點，終點，
一般走一步沒有遇到斜線，中點就是終點， 遇到了的話，路徑就包含了斜線 ,終點坐標計算也要包含斜線的坐標。k ： 定義x 軸向右增大，y軸 向下增大，定義 k = x-y；
d ： 定義為步數。
看下圖：
2566000-f8f59baffd4eb418.png
黃色的線：k線 （注意這些線）
深藍色的線：snake
淺藍色的數字：d (步數)
紅色的線：算法求出的問題的解（其實這個解有多個這只是求了其中一條）
怎么冒出來的這個k？ 所有k相同的點組成了一條線，他們組成了對角線。并且對于k，我們可以使用一個記錄的數組V，用k作為該數組的index，x為value，這樣我們可以計算求得 y值
這個算法父問題的求解歸結為子問題的求解。要知道d=5時所有k對應的最優(yōu)坐標，必須先要知道d=4時所有k對應的最優(yōu)坐標，要知道d=4時的答案，必須先求解d=3，以此類推。
思考：
如何使用最小d（步數） 到達終點（N，M），可以得到外循環(huán)。
接下來我們想想如何到達point（x，y）？ 設 k = x - y，那么能到達點（x，y）的 只能從k-1 或者 k+1兩條對角線上到k上，步數的遞增，內循環(huán)應該是k ，內層循環(huán)完畢的結果就是，在步數為d，求得對角線k能到達的最遠的x坐標。每向下或向右一步，坐標必然會從一條k線上移動到另外一條k線上，也就是說步數固定情況下，k的改變，我們可以求出相應的移動方向從而確定路徑，內循環(huán)就是k遞增，找到最快一條到達終點（N,M）的路，目的就達成了
上偽代碼好好理解下：
偽碼分析
一般到這里就會很多的疑惑，很懵逼：
我們拆分下：
-
最外面這個循環(huán)
//d 是步數，N 是字符的長度6 ，M 是字符長度7 , //縱然 d 一直右向，再向下，經過斜線，也是大于不了N+M 的 for (int d = 0; d<= N +M ;d++){ ··· } 里面這層循環(huán)
- k = x-y ； 我們可以通過x 求y ，v[]數組里面以k為index,存儲最優(yōu)坐標的x值，取的時候只要知道k值，因為v[k] =x;通過有y =v[k]-k 就可以算出y；
k 結合圖形，我們從（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步到達終點（x,y），假設途中經過 一個 3個斜線，經過橫線 i 個,經過豎線 j 個
則x = i+3,y = j+3;終點:（x，y）=>（i+3，j+3）
假設 d 是奇數，i+j 必然是奇數
由k = x-y = i +j +6;
得k 為奇數，d 為奇數，k 只能為奇數，
所以內循環(huán)時 ，k +=2（看圖，這句話的意思是一個方格不能從對角線到對面的點，不是向下，就是向右）
// 每一步遞增
for (int d = 0; d<= N +M ;d++){
//在每一步下面的各個k的取值，k+=2 （見上面地三點）
for( int k = -d ;k <= d ;k +=2){
// 是否向下
//這里注意看圖上黃色斜線，起點k=0時；k= -1 是向下一步，當k=-d 時必然向下 ，k=d 必然向右，第一步d=1 ,k=-1向下，k = 1 向右。
//v[ ]數組保存了k上的 x ，看圖， 從第一步完成后，執(zhí)行第二步，d =2 ,k = - 2, 0 ,2三個數，
// k = -2 時，向下; k = 0 ，(這時右邊的k線 => v[k+1] =1(第一步記錄v[ ]為1)，左邊的k線 => v[k-1] =0(第一步結束時記錄為零)，
// 所以向下，k =2 , v[k+1] = 0(沒有保存) v[k-1] = 1（第一步保存為1）
// 這樣寫的好處，以k 為基準進行的移動，不會出現(xiàn)重復的情況
bool down = ( k== - d || (k !=d && v[k-1] < v[ k+1] ));
···
//save end point
//保存對應k 的x方向的值（這里的x向右0到7，y向下0到6 ）= 保存d步結束，對應k值上的終點坐標；
//終點坐標(x,y)=> （x=v[k]，y= v[k]-k）
v[k] = xEnd;
}
}
-
整個偽碼流程
//新建集合，用k值保存對應的x v[ 1 ] = 0; //步數遞增 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; //起點，因為每次移動保存是 k+2 ,所以如果這次的index全是奇數，上一次就全是偶數，在一個數組里面不會進行覆蓋 int xStart = v[kPrev] int yStart = xStart - v[kPrev] //中點，之前說的，如果沒有遇到斜線，它是等于終點的 int xMid = down ? xStrat : xStart +1; int yMid = xMid - k； //終點，沒有遇到斜線的樣子 int xEnd = xMid; int yEnd = yMid; //斜線數量 int s= 0 //這就是遇到斜線，只有數據相等，才會是斜線，然后，x,y 各加一 while(xEnd < N && yEnd <M && A[xEnd] ==B[yEnd]){ xEnd++; yEnd++; s++; } // 保存到數組 v[k] = xEnd; //到了最終點（N,M）,找到了最短步數的方案 if(xEnD >= N && yEnd > = M){ //跳出循環(huán) } } }
如果看了我注釋還是沒有懂，我推薦幾個網址：
外文的博客,加載有點慢
從DiffUtil到Myers'差分算法
Git是怎樣生成diff的：Myers算法
java實現(xiàn)
算法的論文
如果還沒有懂，結合圖案，多讀幾遍，注意他的每走一步其實就是k線上切換。
