算法簡述
最長上升子序列(Longest Increasing Subsequence, 簡稱LIS)是dp中比較經(jīng)典的一個(gè)算法模型, 它有一種樸素的算法O(n^2)和一種優(yōu)化版的算法(nlogn)實(shí)現(xiàn), 通過它, 我們可以進(jìn)一步了解dp的思想.
題目鏈接
pku-2533 Longest Ordered Subsequence
題意
給定一個(gè)長度為1000以內(nèi)的數(shù)組,每個(gè)元素范圍都在[0,10000]的整數(shù),求這個(gè)數(shù)組的LIS.
解法
記數(shù)組為a[0...n-1],算法很直接,具體如下:
- 狀態(tài)定義:
dp[i]代表以第i項(xiàng)為結(jié)尾的LIS的長度. - 狀態(tài)轉(zhuǎn)移:
dp[i] = max(dp[i], max(dp[j]) + 1) if j < i and a[j] < a[i] - 狀態(tài)初始化:
dp[i]=1 - 時(shí)間復(fù)雜度:
狀態(tài)數(shù)為n, 每次轉(zhuǎn)移復(fù)雜度是O(n), 所以算法總復(fù)雜度是O(n^2)
核心代碼：
for(i = 0; i < n; ++i) {
for(j = 0; j < i; ++j) {
if(a[j] < a[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
算法優(yōu)化
再來看一道題:
題目鏈接:
題意:
這題是一個(gè)經(jīng)典的布線問題, 如下圖所示: 左右各有n(n<40000)個(gè)點(diǎn), 原本左邊的每個(gè)點(diǎn)分別跟右邊的一個(gè)點(diǎn)相連(不會(huì)有兩個(gè)左邊的點(diǎn)連同一個(gè)右邊的點(diǎn)), 要求我們拆除一部分線, 保留盡可能多的線, 使得剩下的線兩兩不能有交點(diǎn).
解法:
記左邊的兩個(gè)點(diǎn)為i, j且i < j, 與之相連的右邊的點(diǎn)分別為a[i], a[j], 則兩條線不相交的充要條件就是: a[i]<a[j], 于是這個(gè)問題轉(zhuǎn)化成了經(jīng)典的LIS.
但是這題與上題最大的差別就在于: 數(shù)組的長度太大了, 由1000變到了40000, 于是O(n^2)復(fù)雜度基本只有超時(shí)的命運(yùn), 所以我們必須想辦法優(yōu)化.
更優(yōu)的算法
下面介紹一種O(nlogn)的LIS算法:
- 記數(shù)組為a[0...n-1];
- 狀態(tài)定義:
dp[i]代表LIS的第i項(xiàng)最小值, dpLen代表當(dāng)前dp數(shù)組的長度; - 狀態(tài)轉(zhuǎn)移:
dp初始為空數(shù)組, 我們按a數(shù)組元素的下標(biāo)順序進(jìn)行掃描, 假設(shè)現(xiàn)在掃描到a[i], 先找到dp數(shù)組中第一項(xiàng)大于或等于a[i]的元素, 記為dp[j]; 將dp[j]更新成a[i]即可; 如果dp數(shù)組中沒有元素比a[i]大的話, 那么直接將a[i]插入到dp數(shù)組的尾部,再更新dp數(shù)組長度; - 整個(gè)數(shù)組的LIS結(jié)果就是dpLen.
- 需要注意的是, 雖然dp數(shù)組最終長度就是LIS, 但是里邊的元素并不是真正的子序列, 如果要求輸出這個(gè)序列, 加上一些反向追蹤變量就能得到了. 但是如何求LIS的數(shù)量呢?
- 剛開始dp數(shù)組為空,顯然是單調(diào)遞增數(shù)組, 而后面的每一步替換或者尾部插入執(zhí)行都不影響其單調(diào)遞增的特性, 所以每次定位到dp[j]可以用二分法, 復(fù)雜度是 O(logn)
- 整體算法復(fù)雜度:
狀態(tài)轉(zhuǎn)移次數(shù)為n, 每次狀態(tài)轉(zhuǎn)移代碼都是logn, 所以總復(fù)雜度為O(nlogn).
算法步驟示例:
假設(shè)a = [4, 2, 6, 3, 1, 5], 初始dp=[], 具體算法運(yùn)行步驟如下:
- a[0]=4 => dp=[4];
- a[1]=2 => dp=[2];
- a[2]=6 => dp=[2, 6];
- a[3]=3 => dp=[2, 3];
- a[4]=1 => dp=[1, 3];
- a[5]=1 => dp=[1, 3, 5];
所以這個(gè)a數(shù)組的LIS就是len(dp)=3. 從運(yùn)行步驟里可以看出, 如果一個(gè)數(shù)很小, 可以作為LIS的頭部或者中部, 讓后面的數(shù)字更容易接到它后面, 以此增大LIS長度; 而一個(gè)數(shù)非常大, 則可以很容易接到LIS的尾部, 也一樣能增大LIS長度; 所以讓它們找準(zhǔn)自己的定位還是非常重要的.
核心代碼:
dpLen = 0;
for (i = 0; i < n; ++i) {
int idx = lower_bound(dp, dp + dpLen, a[i]) - dp;
dp[idx] = a[i];
if (idx + 1 > dpLen) {
dpLen = idx + 1;
}
}
完整代碼
ps: Java里沒有提供類似lower_bound或者upper_bound
之類的方法, 還是挺遺憾的, 所以這題代碼就用C++了.
