假設(shè)某大學(xué)有一個活動室，我是這個活動管理員。某天，有6個社團都提出了使用活動室的要求，并告知了他們希望使用活動室的時間段（他們之間相互不知道對方的要求，因此時間安排是沒有相互商量過的，可能有重疊）?；顒邮也荒芡瑫r被兩個以上社團使用。作為管理員，我無法每次都滿足所有人的要求，但我想盡量提高活動室的使用率，那么，我如何選取某幾項活動，使得活動室的使用時間最長呢？
如上圖，假設(shè)上圖是某一次這些社團的要求（假設(shè)0是正午12點），各顏色條分別是各個社團的使用時間計劃。那么，我應(yīng)該如何分配活動室呢？顯然，如果給了社團5，其它社團就不能再使用該活動室了，這時活動室的使用時間是從2點到8點，共使用了6個小時。但這不是最長的使用時間組合。如果將活動室分配給1、3、4、6，那么除了4點到5點之間活動室是空的之外，其它時間活動室都被使用了，一共使用時間是8個小時。
（其實在《算法導(dǎo)論》一書的第16章第一節(jié)中，也提到一個活動選擇問題。這里說的活動選擇問題與書中的不一樣。這兩個問題要求不一樣。那個問題將在貪婪算法相關(guān)的內(nèi)容中討論）
使用蠻力法，不會是一種好的方法。這一點就不過多論證了。
這是個最優(yōu)化問題。我們探索下，會發(fā)現(xiàn)這個問題的最優(yōu)解，是有可能表示成子問題最優(yōu)解的遞歸解的。假設(shè)Tij是一個從i點到j(luò)點的時間段，這個時間段內(nèi)，最長的使用時間是Sij。Sij的計算中用到的活動，必須是要求整個活動時間被包括在Tij中的，不能越過這個時間限。我們就稱Vij是這樣一個集合，其中包含了所有時間范圍被完全包含在Tij范圍內(nèi)的活動。
假設(shè)對于i點到j(luò)點Tij，如果i=j，那么很顯然Sij就是0。如果i不等于j，那么最長使用使用時間Sij可能是j-i個小時，也就是有一個活動從i點一直搞到j(luò)點，那么挺好，就選擇這個活動就行了。但如果不存在這么長時間的活動，那么，我們可以試著把這個時間分成兩個部分Tik和Tkj，它們分別最長的使用時間是Sik和Skj。令S'=Sik+Skj，我們知道，當(dāng)k從i到j(luò)依次取值時，可以得到各組不同的Sik和Skj，Sij肯定是S'中取最大的那個值。為什么呢？因為如果沒有一個在Tij時間內(nèi)段的活動能充滿整個Tij時間段的話，那么Vij內(nèi)的任何一個活動單獨放到Tij時間段內(nèi)，那么在這個時間段的前端和后端，至少會出現(xiàn)一個空白的沒被使用的時間，如下圖：
所以，直感上看，就可以把空白的時間段取出來，看這個時間段內(nèi)還能不能再按排一些活動。只要沒有一個活動可以填滿整個時間段，那么最大使用時間就是Vij內(nèi)多個活動時間拼接成的。那么對于從i到j(luò)內(nèi)的每一個時間點k，這個點左右兩邊Tik和Tkj內(nèi)會分別安排一些活動（因為每個活動都是從整點開始到整點結(jié)束，而且各活動使用活動室的時間也不能重疊。但可能Vik或Vkj會為空），就分別能得到Sik和Skj。只要對每一個可能的k值進行檢查，那么最大時間肯定就是其中的一個。
因此，我們可以得出Sij的計算方法：
- 如果i=j，則 Sij=0
- 否則，如果存在一個活動的時候長度恰好為Tij，則Sij=j-i
- 否則，Sij＝max{Sik+Sij} ，其中、k從i到j(luò)依次取值。
現(xiàn)在，我們已經(jīng)得到了這個問題最優(yōu)解的一個遞歸形式的解。遞歸式中包含了子問題的最優(yōu)解。（關(guān)于子問題是否是最優(yōu)解，可以用《算法導(dǎo)論》中的"剪切粘貼法"來考慮）。這是能用動態(tài)規(guī)劃來解決的問題的第一個特征。
然后再看，如果我們根據(jù)這個遞歸直接翻譯寫出遞歸程序，那么，對于會出現(xiàn)很多重復(fù)的計算。比如，當(dāng)我們計算S09時，會用到S01、S02、S03、S04、......、S07、S08，再計算S08時，又會用到S01、S02、S03、S04、......、S07。以此類推，這個表達式中存在非常多的重復(fù)計算，計算量很大。嗯，有很多重疊的子問題，這是能用動態(tài)規(guī)劃來解決的問題的第二個特征。
那么，根據(jù)動態(tài)規(guī)劃的方法，就應(yīng)該用從底向上的方法來解決這個問題，先計算小區(qū)間的值，并存儲起來，然后再利用已經(jīng)得到的小區(qū)間的值來計算大區(qū)間的值。最終得到原問題的最優(yōu)解。如下圖：
格子[i，j]表示從i點到j(luò)點，最大利用時間值是多少?；业舻牟糠质菬o效值，因為此時i值大于j值，沒有實際意思。這個表，我們從左到右計算每一列的值，就是用的從底向上的方法，最終可以地推出結(jié)果[0，9]的值是8.
在計算最大時間的過程中，將每次使得Sij最大時的K值記錄下來，存儲到K[i][j]中去，Sij得出來之后，就可以到出一個K[i][j]的表，根據(jù)這個表，可以得到如何不斷地將時間劃分成最優(yōu)的兩段，直至?xí)r間段內(nèi)有活動充滿該時間段，或是時間段內(nèi)不存在任何活動。有了這個時間劃分，我們就可以從這些時間段中分別相應(yīng)的活動，這樣，問題就最終得到了解決。