假設你是搞錢小能手，搬磚之餘週末還想去兼職，現在有n份工作，每份工作的起始時間儲存在陣列startTime中、結束時間儲存在陣列endTime中、能獲取的報酬儲存在陣列profit中，那麼你該怎樣挑選在時間上不衝突的減重工作從而獲取最多的報酬，返回該報酬。
注意，
在這裡陣列startTime已經按照從小到大的順序排好序。
假定現在有5份工作，startTime = {1，2，3，4，6}，endTime = {3，5，10，6，9}，profit = {20，20，100，70，60}，如圖所示：
那麼你應該挑選1、4和5這三份工作，
其時間不衝突且能獲得最多的報酬
，其值為150。
想一想該怎樣解決問題。
子問題與選擇
和上一個題目一樣，你首先應該找出子問題是什麼，子問題與原始問題的依賴關係是什麼。
找出子問題的關鍵在於每一步的選擇。
我們首先考慮第一份工作，此時你有兩種選擇，接受和不接受。
如果接受第一份工作，
那麼這就意味著你不能再接受第二份工作，因為這兩份工作在時間上是衝突的
，此時問題就變為了在剩下的第3份工作中進行挑選從而確保獲取最多的報酬，注意，該子問題的本質和原始問題一樣。
如果不接受第一份工作，那麼接下來的問題就變為了從剩下的4份工作中進行挑選從而確保獲取最多的報酬，注意，該子問題的本質同樣和原始問題一樣。
現在我們找到了兩個子問題，那麼原始問題的解與子問題的解有什麼關係呢？
很簡單，原始問題的解無非就是這兩個子問題解中較大的那個：
從這張圖中你可以看到：
原始問題的解 = max（20 + 子問題1的解， 子問題2的解）
現在你應該能看出原始問題與子問題之間的關聯了，實際上這張圖狀態空間樹還可以繼續畫下去，但由於該樹過大因此我們僅從上圖中的第一種選擇繼續，那麼其狀態空間樹為：
當所有的工作都選擇完畢時就到達葉子節點，此時我們可以計算出從根節點到當前葉子節點整條路徑上的選擇能得到的報酬總和，從上圖可以看到最多的報酬是150。
現在你應該清楚的知道該怎樣我們是怎樣一步步將問題不斷的分解為更小的子問題，然後利用子問題的解來得到原始問題的解了。
自頂向下遞迴程式碼
上圖中每個方框都是一個子問題，其決定因素在於當前需要對哪個工作進行選擇，假設當前我們要對第i個工作進行選擇，因此我們可以對問題進行定義：
int jobScheduling（int i）；
該函式的含義是從第i個到最後一個工作中進行選擇所能獲取的最多報酬是多少，基於上述討論以及狀態空間樹你可以很容易的寫出這樣的遞迴程式碼：
vector
startTime；vector
endTime；vector
profit；int jobScheduling（int i） { // 遞迴出口：此時沒有工作可選，因此可獲得的報酬是0 if （i == startTime。size（）） return 0； // 第一種選擇，接受當前的工作 int next； bool find = false； int resa = 0； // 找到下一個與當前工作時間不衝突的工作 for （next = i + 1； next
注意看該遞迴函式的結果僅僅由一個引數決定，那就是引數i，而i的取值範圍為［0， startTime。size（）］，也就是說最多隻有startTime。size（） + 1個子問題，而上述遞迴程式碼存在大量重複計算問題，這點從上述狀態空間樹也能看出來：
圖中標註的這兩個子問題其實是完全一樣的，但會被上述遞迴程式碼重複求解。
基於此我們可以增加cache進行最佳化：
int jobScheduling（int i） { if （i == startTime。size（）） return 0； // 如果當前子問題之前解決過則直接返回 if （cache［i］） return cache［i］； int next； bool find = false； int resa = 0； for （next = i + 1； next
現在每個子問題只需要被求解一次，接下來我們著手將上述自定向下的遞迴程式碼轉為自底向上的非遞迴程式碼。
自底向上動態規劃
注意看該遞迴函式，其決定因素只有引數i，引數i的所有可能的情況只有startTime。size（） + 1個，因此我們可以定一個startTime。size（） + 1大小的一維陣列dp：
vector
dp（startTime_。size（） + 1， 0）；
接下來我們要求解最小子問題，最小子問題就是上述遞迴程式碼的遞迴出口：
if （i == startTime。size（）） return 0；
也就是說dp［startTime。size（）］應該等於0，而這已經包含在了陣列初始化程式碼中了。
接下來我們利用for迴圈手動構造出所有引數i的可能，將上述遞迴程式碼中非遞迴出口部分置於該for迴圈中，最終我們到了完整的動態規劃程式碼：
int jobScheduling（vector
& startTime， vector
& endTime， vector
& profit） { vector
dp（startTime_。size（） + 1， 0）； for （int i = startTime。size（） - 1； i >= 0； i——） { int next； bool find = false； int resa = 0； for （next = i + 1； next
開啟App看更多精彩內容