彻底理解动态规划：赚钱的兼职

这是动态规划主题的第二篇，本文的题目是赚最多钱的兼职。

假设你是搞钱小能手，搬砖之余周末还想去兼职，现在有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];
}