問題與基本方法
定義 2.4.1
(嚴格遞增子序列與最長遞增子序列問題)
設 是取值屬於全序集合的有限序列。嚴格遞增子序列選取下標 ,並要求 ;所選位置不必相鄰,亦不能重複選取同一個值。問題是求一個長度 最大的這類子序列(稱為解)及其長度。當 ,答案是長度 及空解。
下文計算數值比較次數,並假設每次比較耗時為常數。直接的動態規劃清楚展示狀態的選擇:狀態必須記錄子序列在哪裏結尾,因為只有最後一個值才限制它如何延長。
定理 2.4.2
(最長遞增子序列的二次動態規劃)
對 ,令 為以下標 結尾的嚴格遞增子序列之最大長度,則
當 ,最優長度是 。對每個 的 ,儲存一個達到最大值的下標 ,再由達到 的下標沿這些儲存的下標回溯並反轉,便得到一個解。此方法使用 次比較及 空間。
證明
(按結尾下標歸納)
固定 ,取一個以 結尾、長度達到 的子序列。若它只有一項,則 ,而由下面的反向不等式可知不存在合格的 。否則它有倒數第二個下標 ,且 ;其首 項構成以 結尾的嚴格遞增子序列,故 。反過來,對任何滿足 及 的 ,在以 結尾的最優子序列後加上 是合法的,長度為 ,故 。兩個方向合起來,按 歸納便證得遞推式; 處理不存在合格 的情況。
每個嚴格遞增子序列都在某處結尾,因此最優長度是 。對 的下標 ,沿所儲存的前驅走一步,會到達 值恰好小一的下標,所以走 步後到達 的下標;將收集到的下標反轉,便得到遞增的下標及嚴格遞增的值。需要比較的下標對 至多有 個,而陣列 與指標都只有 項。
概念視角組合
位置圖上的最長路徑
當 且 時,畫一條邊 。一列下標是有向路徑,當且僅當每對相鄰下標在位置和數值上都遞增;把不等式連起來,這與「嚴格遞增子序列」完全相同。因此問題就是這個無環圖上的最長路徑問題, 是以 結尾的路徑所含頂點數的最大值。遞推式就是按下標次序計算最長路徑的常用遞推式,而二次的比較次數,就是檢視每條可能的邊的代價。下一節的方法並不建立這個圖。
快速檢查
(求序列 的 ,並寫出最優長度。)
由左至右套用遞推式。
解答 · 答案
。 只有 合格,故 。 同樣只有 合格,故 。 之前的值都較小,而 ,故 。最優長度是 ,例如 或 。
最小末尾值與二分搜尋
如果只需長度,可壓縮所需資訊。
定義 2.4.3
(最小末尾值清單)
固定前綴 ,令 為其中嚴格遞增子序列的最大長度。對每個 ,最小末尾值 是此前綴中長度為 的嚴格遞增子序列之末尾值的最小值。由於前綴有限,每個最小值都存在;又因為長度 的子序列有每個較短長度的前綴,所以每個 都有子序列達到。最小末尾值清單是 ;當 時為空。
定理 2.4.4
(最小末尾值不變量與更新規則)
設 是前綴 的最小末尾值清單,則 。令 ,並令 為第一個滿足 的下標;若沒有,取 。前綴 的最小末尾值清單,是將 設為 ( 時為新增的最後一項),其餘各項不變而得。因此處理完整個輸入後,清單的長度就是最優長度。
證明
(只有一項會改變)
嚴格性。 達到 的子序列,其長度 前綴的末尾較小,因此 。
哪些長度能以 結尾。 舊的子序列在較長前綴中仍然存在,所以各項只會變小;變小需要新的子序列,它必須以下標 (值為 )結尾。設這樣的子序列長度為 。刪去最後一項,便得到舊前綴中長度 、末尾值小於 的子序列,所以 。由於 嚴格遞增,小於 的項恰是 ,故 ,即 。另一方面,若 ,則 ,在達到 的子序列後加上 ,便得到以 結尾、長度為 的子序列;若 ,單項 的長度為一。所以以 結尾的子序列可有直至 的每個長度,卻不會更長。
對各項的影響。 當 ,已有 ,故以 結尾的新子序列無法降低 。當 ,不存在該長度的新子序列。當 ,新候選值 滿足 ,故該項變為 (若 則不變)。若 ,新清單多一項 ;不可能形成更長的子序列,因為舊前綴的最大長度是 。從空前綴出發按 歸納,便證得此規則,而最後的 就是最優長度。
證明透視
更新規則的力量從何而來
唯一不顯然的一步,是只用一個比較 ,便為每個新子序列的長度定出上界 。清單的嚴格性被用了兩次:它令小於 的項構成清單的一段前綴,所以可以用二分搜尋找到分界點 ;它也把界 化為 。問題本身的嚴格性則經由分界點的選擇進入論證:等於 的項並不小於 ,因此不會被延長,而是由 取代,而不是產生更長的子序列。論證得以完結,是因為 、、 三種情況涵蓋每一項,而只有 會改變。
這裏使用下界搜尋,即尋找首個末尾值至少為 的位置。相等值不得延長嚴格遞增序列的長度;本更新規則會替換相等的末尾值。若要求非遞減子序列,則應改找首個嚴格大於 的末尾值,並相應修改不變量和比較;兩種規格不能互換。
反例模式
用上界搜尋會算出錯誤的長度
假設改為搜尋首個嚴格大於 的末尾值,但規格仍是嚴格遞增。對 ,清單起初為空,第一個 被新增:。第二個 沒有嚴格更大的末尾值,因此再次新增:,第三個 令清單成為 。此方法報告長度 ,但嚴格遞增子序列不能重複同一個值,真正的最優長度是 。修正方法是採用更新規則中的下界搜尋:第二個和第三個 ,首個至少為 的末尾值都是 ,所以 被 取代,清單保持 ,長度為 。上界搜尋版本算出的其實是最長非遞減子序列的長度。
重構真正的子序列
中的值本身未必按輸入次序出現。例如輸入 的最終清單是 ,但 在 之後。要重構解,儲存 ,即實現目前 的某個子序列的末尾下標,並為每個已處理位置儲存不可變的前驅指標 。
命題 2.4.5
(以前驅指標重構解)
處理項目 、分界點為 時,若 便令 ,若 則令 (終止標記),然後令 。處理完最後一項後,從 沿指標回溯至 ,再將收集到的下標反轉。當 ,結果是長度恰為 的嚴格遞增子序列,因此是一個解。當 ,直接返回空序列,不查找 。整個方法使用 次比較及 空間。
證明
(指標記錄長度逐步減一的鏈)
斷言:任何時刻, 都是某個長度為 、末尾值為 的嚴格遞增子序列的末尾下標,而由 出發的指標鏈列出它的 個下標。處理項目 時, 所指的子序列末尾值為 ,且其末尾下標早於 ,所以所儲存的前驅 早於 ,其值亦嚴格較小。先前儲存的指標 從不被改寫,因此把 設為 時,由 出發的鏈不變;由 出發的鏈比由 出發的鏈多一個下標,合共 個。按已處理的項目歸納便證得斷言,而最後由 出發的鏈有 個下標,反轉後下標遞增、值嚴格遞增。
每個項目的二分搜尋使用 次比較,故合共 次。陣列 、、 都只有 項。這些界限假設比較及下標操作均耗常數時間。
反例模式
末尾值清單不是解
斷言:最終的末尾值清單本身就是一個最長遞增子序列。對輸入 ,清單依次為 、、,最終清單 的長度 是正確的。但輸入中 在 之後,所以 並不是子序列;長度為二的嚴格遞增子序列只有 。所儲存的下標 同樣顯示失敗,因為下標 並不小於下標 。修正靠已儲存的指標:項目 (值為 )儲存了 ,從 沿指標回溯得到下標 ,即解 。
例題
例題 2.4.6
(七項輸入的最小末尾值與解)
依次處理 。最小末尾值清單依次為
最終長度是 。由最後一項的已儲存指標回溯得到 ,所以一個解是 ,下標為 。此處末尾值清單碰巧構成子序列;正如上面的反例所示,這並非一般保證。
例題 2.4.7
(四個數值的二次表格)
對 由左至右計算 。。 之前沒有更小的值,故 。 只有 合格,故 ,前驅為 。 同樣只有 合格,故 ,前驅為 。最優長度是 。沿下標 的指標得到下標 ,即解 ;沿下標 的指標得到下標 ,即解 。兩者都是最長的,可見解並不唯一。
例題 2.4.8
(邊界情況:空輸入與重複值)
當 ,清單保持為空,長度為 ,解為空,亦不查找 。
對 :清單依次為 、;處理第二個 時,首個至少為 的末尾值是 ,所以 被相等的值 取代,清單仍是 ,而 變為下標 。處理值 時,沒有末尾值至少為 ,故 ,清單成為 ,且 。指標給出鏈 ,所以解的下標是 ,值為 。重複的 只被使用一次,長度為 。
常見錯誤
常見錯誤
(以最後一個狀態代替最大狀態作答)
狀態 描述恰好以 結尾的子序列,所以答案是 ,而不是 。對 ,各狀態為 ,因為 之前沒有更小的值。最後一個狀態是 ,但最優長度是 ,在下標 達到。
常見錯誤
(處理完才從末尾下標陣列讀取前驅)
後來的項目可能覆寫 (),所以最終的陣列 並不是一條位置鏈。對 ,處理過程中 依次為 、、,最後是 。下標 並非遞增。項目 的前驅在處理它時已儲存為 ,鏈 給出正確的解 。必須在處理項目 的當刻儲存 。
習題
快速檢查
(對 套用嚴格遞增算法,求長度並與最長非遞減長度比較。)
使用下界搜尋。
解答 · 答案
嚴格遞增長度是 :每個新的 都替換第一個末尾值。非遞減長度是 ,因為三個相等值都可依次選取。
快速檢查
(逐項計算 的嚴格最小末尾值清單,給出一個最長解及其下標。)
由左至右處理,每次替換第一個至少等於新值的末尾值。
解答 · 答案
清單為 、、、。最優長度是 ;例如 的下標是 。指標方法也能重構有效的解。
快速檢查
(若要求輸出實際輸入下標,為何只儲存最終末尾值不安全?給出本節最短反例,並解釋需要甚麼額外資訊。)
把末尾值清單與輸入次序比較。
解答 · 答案
對 ,最終末尾值 的輸入次序顛倒。儲存每個末尾值目前的結尾下標,以及每個已處理位置的固定前驅指標;沿最終下標的指標鏈回溯,不能直接把末尾值清單當作解。