在Partially order set(偏序集)有一個非常NX的定理叫Dilworth Theorem。上圖是偏序集的一個Hasse diagram，偏序集的定義是 偏序是在集合X上的二元關系≤，它滿足自反性、反對稱性和傳遞性。即，對于X中的任意元素a,b和c，有: 自反性：a≤a; 反對稱性：如果a≤b且b≤a，則有a=b; 傳遞性：如果a≤b且b≤c，則a≤c 。 帶有偏序關系的集合稱為偏序集。 令(X,≤)是一個偏序集，對于集合中的兩個元素a、b，如果有a≤b或者b≤a，則稱a和b是可比的，否則a和b不可比。 在X中，對于元素a，如果任意元素b，由b≤a得出b=a，則稱a為極小元。 一個反鏈A是X的一個子集，它的任意兩個元素都不能進行比較。 一個鏈C是X的一個子集，它的任意兩個元素都可比。 下面是兩個重要定理： 定理1 令（X,≤）是一個有限偏序集，并令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。 其對偶定理稱為Dilworth定理： 定理2 令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。 搞清楚了反鏈和鏈的定義，就能夠很好的從Hasse Diagram中得到理解。鏈就是從縱向的角度看 Hasse Diagram ,反鏈是從橫向的角度看Hasse Diagram。 定理一，就是至少有r行構成反鏈關系。 定理二，就是至少有m列構成鏈關系。    我們來考慮一個導彈攔截問題，就是求一個序列的最長不上升子序列，以及求能最少劃分成幾組不上升子序列。 很顯然第一個是動態規劃，動態規劃的過程就是求Hasse Diagram的過程！！！    第二問就是求最少能夠劃分成幾個鏈，根據定理2 [...]
文章來源:http://www.lxlsosi.tk/2011/05/26/%e5%81%8f%e5%ba%8f%e9%9b%86-dilworth-%e5%ae%9a%e7%90%86-poj-1065-3636-1548/