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

這是動(dòng)態(tài)規(guī)劃主題的第二篇，本文的題目是賺最多錢的兼職。

假設(shè)你是搞錢小能手，搬磚之余周末還想去兼職，現(xiàn)在有n份工作，每份工作的起始時(shí)間保存在數(shù)組startTime中、結(jié)束時(shí)間保存在數(shù)組endTime中、能獲取的報(bào)酬保存在數(shù)組profit中，那么你該怎樣挑選在時(shí)間上不沖突的減重工作從而獲取最多的報(bào)酬，返回該報(bào)酬。

注意，在這里數(shù)組startTime已經(jīng)按照從小到大的順序排好序。

假定現(xiàn)在有5份工作，startTime = {1,2,3,4,6}，endTime = {3,5,10,6,9}，profit = {20,20,100,70,60}，如圖所示：

那么你應(yīng)該挑選1、4和5這三份工作，其時(shí)間不沖突且能獲得最多的報(bào)酬，其值為150。

想一想該怎樣解決問題。

子問題與選擇

和上一個(gè)題目一樣，你首先應(yīng)該找出子問題是什么，子問題與原始問題的依賴關(guān)系是什么。

找出子問題的關(guān)鍵在于每一步的選擇。

我們首先考慮第一份工作，此時(shí)你有兩種選擇，接受和不接受。

如果接受第一份工作，那么這就意味著你不能再接受第二份工作，因?yàn)檫@兩份工作在時(shí)間上是沖突的，此時(shí)問題就變?yōu)榱嗽谑Ｏ碌牡?份工作中進(jìn)行挑選從而確保獲取最多的報(bào)酬，注意，該子問題的本質(zhì)和原始問題一樣。

如果不接受第一份工作，那么接下來的問題就變?yōu)榱藦氖Ｏ碌?份工作中進(jìn)行挑選從而確保獲取最多的報(bào)酬，注意，該子問題的本質(zhì)同樣和原始問題一樣。

現(xiàn)在我們找到了兩個(gè)子問題，那么原始問題的解與子問題的解有什么關(guān)系呢？

很簡單，原始問題的解無非就是這兩個(gè)子問題解中較大的那個(gè)：

從這張圖中你可以看到：

原始問題的解 = max(20 + 子問題1的解, 子問題2的解)

現(xiàn)在你應(yīng)該能看出原始問題與子問題之間的關(guān)聯(lián)了，實(shí)際上這張圖狀態(tài)空間樹還可以繼續(xù)畫下去，但由于該樹過大因此我們僅從上圖中的第一種選擇繼續(xù)，那么其狀態(tài)空間樹為：

當(dāng)所有的工作都選擇完畢時(shí)就到達(dá)葉子節(jié)點(diǎn)，此時(shí)我們可以計(jì)算出從根節(jié)點(diǎn)到當(dāng)前葉子節(jié)點(diǎn)整條路徑上的選擇能得到的報(bào)酬總和，從上圖可以看到最多的報(bào)酬是150。

現(xiàn)在你應(yīng)該清楚的知道該怎樣我們是怎樣一步步將問題不斷的分解為更小的子問題，然后利用子問題的解來得到原始問題的解了。

自頂向下遞歸代碼

上圖中每個(gè)方框都是一個(gè)子問題，其決定因素在于當(dāng)前需要對(duì)哪個(gè)工作進(jìn)行選擇，假設(shè)當(dāng)前我們要對(duì)第i個(gè)工作進(jìn)行選擇，因此我們可以對(duì)問題進(jìn)行定義：

int jobScheduling(int i);

該函數(shù)的含義是從第i個(gè)到最后一個(gè)工作中進(jìn)行選擇所能獲取的最多報(bào)酬是多少，基于上述討論以及狀態(tài)空間樹你可以很容易的寫出這樣的遞歸代碼：

vector<int> startTime;
vector<int> endTime;
vector<int> profit;

int jobScheduling(int i) {
 // 遞歸出口：此時(shí)沒有工作可選，因此可獲得的報(bào)酬是0
 if (i == startTime.size()) return 0;

 // 第一種選擇，接受當(dāng)前的工作
 int next;
 bool find = false;
 int resa = 0;
 // 找到下一個(gè)與當(dāng)前工作時(shí)間不沖突的工作
 for (next = i + 1; next < startTime.size(); next++) {
  if (endTime[i] <= startTime[next]) {
   find = true;
   break;
  }
 }
 resa = find ? jobScheduling(next) + profit[i] : profit[i];

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

 return max(resa, resb) ;
}

注意看該遞歸函數(shù)的結(jié)果僅僅由一個(gè)參數(shù)決定，那就是參數(shù)i，而i的取值范圍為[0, startTime.size()]，也就是說最多只有startTime.size() + 1個(gè)子問題，而上述遞歸代碼存在大量重復(fù)計(jì)算問題，這點(diǎn)從上述狀態(tài)空間樹也能看出來：

圖中標(biāo)注的這兩個(gè)子問題其實(shí)是完全一樣的，但會(huì)被上述遞歸代碼重復(fù)求解。

基于此我們可以增加cache進(jìn)行優(yōu)化：

int jobScheduling(int i) {
 if (i == startTime.size()) return 0;

  // 如果當(dāng)前子問題之前解決過則直接返回
 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);

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

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

自底向上動(dòng)態(tài)規(guī)劃

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

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

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

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

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

接下來我們利用for循環(huán)手動(dòng)構(gòu)造出所有參數(shù)i的可能，將上述遞歸代碼中非遞歸出口部分置于該for循環(huán)中，最終我們到了完整的動(dòng)態(tài)規(guī)劃代碼：

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];
}