大家好，我是小風哥，休息了將近一周后終于滿血復活了，關于陽康的故事下篇再聊，今天主講技術。

這是動態規劃主題的第二篇，本文的題目是賺最多錢的兼職。

假設你是搞錢小能手，搬磚之余周末還想去兼職，現在有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<int> startTime;
vector<int> endTime;
vector<int> 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 < startTime.size(); next++) {
  if (endTime[i] <= startTime[next]) {
   find = true;
   break;
  }
 }
 resa = find ? jobScheduling(next) + profit[i] : profit[i];

    // 第二種選擇，不接受當前的工作
 int resb = jobScheduling(i + 1);

 return max(resa, resb) ;
}

注意看該遞歸函數的結果僅僅由一個參數決定，那就是參數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 < startTime.size(); next++) {
  if (endTime[i] <= startTime[next]) {
   find = true;
   break;
  }
 }
 resa = find ? jobScheduling(next) + profit[i] : profit[i];

 int resb = jobScheduling(i + 1);

  // 記錄下當前問題的解
 return cache[i] = max(resa, resb) ;
}

現在每個子問題只需要被求解一次，接下來我們著手將上述自定向下的遞歸代碼轉為自底向上的非遞歸代碼。

自底向上動態規劃

注意看該遞歸函數，其決定因素只有參數i，參數i的所有可能的情況只有startTime.size() + 1個，因此我們可以定一個startTime.size() + 1大小的一維數組dp：

vector<int> dp(startTime_.size() + 1, 0);

接下來我們要求解最小子問題，最小子問題就是上述遞歸代碼的遞歸出口：

if (i == startTime.size()) return 0;

也就是說dp[startTime.size()]應該等于0，而這已經包含在了數組初始化代碼中了。

接下來我們利用for循環手動構造出所有參數i的可能，將上述遞歸代碼中非遞歸出口部分置于該for循環中，最終我們到了完整的動態規劃代碼：

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
 vector<int>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 < startTime.size(); next++) {
      if (endTime[i] <= startTime[next]) {
       find = true;
       break;
      }
     }
     resa = find ? dp[next] + profit[i] : profit[i];

     int resb = dp[i + 1];
     dp[i] = max(resa, resb);
 }
 return dp[0];
}