求兩版本之間的差異是一個動態規劃問題
git 能發現任何的改動，但它是怎麼發現的呢？難道它監控了我們對文件的讀寫操作？ git 才沒這麼雞凍……它是通過比較新舊版本，掐指一算算出來的O(∩_∩)O。
首先假設我們只能通過以下3個操作將舊版本演化為新版本：
copy —— 復制舊版本當前行到新版本
insert —— 在新版本中添加一行
delete —— 跳過舊版本當前行
那麼，如下舊版本（左）到新版本（右）：
1 22 333
1 333
可通過
方案一：copy、delete、copy
方案二：delete、delete、delete、insert、insert
演化而來。
舊版本可通過這3個操作演化成任意一個新版本，即使新版本已經面目全非：
假設舊版本有n行，新版本有m行。不管它們每行的內容是什麼，總是可以通過 n次delete 和 m次insert 演化出新版本。
但是，由於 1個copy 能頂替 1個insert+1個delete，所以方案一比方案二少兩個步驟。而且我們實際進行的操作就是步驟最少的方案一（呵呵，人類是最聰明的O(∩_∩)O）。
--------------------------------------------------------------------------------
現在我們有目標了：怎麼得到一個步驟最少的演化方案？為了更清晰地描述演化過程，我們定義兩個下標： i（舊版本行號）、j（新版本行號）。演化過程中會改變這兩個下標：
copy : ++i,++j
insert : ++j
delete : ++i
定義 minPrice[i][j] 為從位置 （i,j） 演化到（n,m） 的最少步驟數（i,j從0開始）；那麼，minPrice[0][0] 就是從舊版本演化到新版本的最少步驟數。
求 minPrice 的遞歸式很容易得出：
--------------------------------------------------------------------------------
如果照這個遞歸式寫一個遞歸算法，那麼遞歸算法會有很多重疊子問題，例如：
minPrice[0][0]、minPrice[0][1]、minPrice[1][0] 都需要計算 minPrice[1][1]。
因此適合采用動態規劃逆向求解。下面我用 java 實現了動態規劃版的 Diff：
E:\temp>java Diff src.txt dest.txt
1 1 1
2 - 22
3 2 333
E:\temp>
