如果你還不會「LCS最長共同子序列」,請先上網學習,確保足夠熟悉了再來讀這一篇文章。
從正常的lcs寫法,我做了3次記憶體簡化
1. lcs2d[n][n] → lcs[n] + backup[n]
在進行lcs填表時,我們可以發現,從頭到尾我們只會存取到lcs2d[i]列與lcs2d[i-1]列,其餘的空間是不需要的,我們可以將lcs2d[i-1]的內容存放於backup[n]中,並且對lcs[n]進行填表,最後再執行swap即可。
程式碼參考:
// a[], b[] 為輸入的兩個陣列
for(i=0; i<N1; i++) {
swap(lcs, bac);
for(j=0; j<N2; j++)
if(a[i]==b[j]) lcs[j+1] = bac[j]+1;
else lcs[j+1] = max(lcs[j+1], lcs[j]);
}
2. lcs[n] + backup[n] → lcs[n] + t + c
目標是把backup[]也省下來。當我們在更新lcs[j+1]時,會需要backup[j]的資料,這是舊的lcs[j], 所以我們可以在前一次迴圈就先把lcs[j]的資料存下來。
for(i=0; i<N1; i++) {
swap(lcs, bac);
for(j=0; j<N2; j++) {
if(a[i]==b[j]) lcs[j+1] = t+1;
else lcs[j+1] = max(lcs[j+1], lcs[j]);
t = lcs[j+1];
}
}
但是這樣寫,t存的依舊是更新過的lcs[j+1],若是將t=lcs[j+1]寫在if之前,又會將接下來需要的t值覆蓋掉。
解決這個問題也很簡單,就像基礎的兩數交換一樣,先存在另一個空間就好
for(i=0; i<N1; i++) {
swap(lcs, bac);
for(j=0; j<N2; j++) {
c = lcs[j+1];
if(a[i]==b[j]) lcs[j+1] = t+1;
else lcs[j+1] = max(lcs[j+1], lcs[j]);
t = c;
}
}
因為Java在變數指派上跟C++有些許不同,所以可以不需要變數c,具體作法結尾再介紹。
3. a[] + b[] → a[]
內層迴圈中的a[i],從頭到尾都不會變,離開迴圈後就不會再用到了,所以我們沒有必要用陣列把它存下來,需要時再接收輸入就行了,這個部分就交給你自己寫囉~
對了,微不足道的優化
內層迴圈內的j+1比j還要多,所以我把迴圈改成這樣
for(j=0; j++<N2;) ...
這樣就能把j+1改成j,j改成j-1了
Java變數指派的特性
先從兩數交換談起,你知道java能一行做完兩數交換嗎?
a = b + (b=a)*0;
因為java會嚴格由左至右運算,所以可以利用這個算式達到兩數交換(這個算式在C++無法達到我們要的效果,因為C++會先算(b=a))
當然同樣的邏輯也可以寫成
a = b | (b=a)&0;
各種寫法都行,只要確保未更新的b先出現,後面多一個0,並且在這個0中將b更新(此時的a絕對還沒被更新)
根據這個概念,java可以將內層迴圈的算式改成:
for(j=0; j<N2; j++)
t = lcs[j+1] | 0&(
a[i]==b[j] ? t+1 : Math.max(lcs[j+1], lcs[j])
);
希望這篇解題報告能幫助到你^_^