彻底理解动态编程：赚钱的小能手，最赚钱的兼职

假设你是赚钱的小能手，周末除了搬砖还想兼职。现在有n个作业，保存每个作业的开始时间。数组StartTime中，结束时间存储在数组EndTime中，能够获得的奖励存储在数组Win中。那么如何选择时间上不冲突的减肥任务才能获得最多的奖励，并把奖励拿回来。

注意这里数组StartTime已经从小到大排序。

假设现在有 5 个作业，StartTime = {1,2,3,4,6}，EndTime = {3,5,10,6,9}，Profit = {20,20,100,70,60 }，如图：

那么你应该选择1、4、5这三个工作，，时间不冲突的，获得最多的补偿，他们的价值是150。

思考如何来解决问题。 子问题和选择

和上一题一样，首先要弄清楚子问题是什么，子问题与原问题之间的依赖关系是什么。

找到子问题的关键在于每一步的选择。

我们首先考虑第一份工作。这时候你有两个选择，接受或者不接受。

如果您接受第一个工作，，那么这意味着您不能接受第二个工作，因为这两个工作在时间上有冲突。这时候问题就变成了剩下的选择下面的第三个工作来保证最大的奖励。请注意，该子问题的本质与原问题相同。

如果你不接受第一份工作，那么接下来的问题就是选择剩下的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 子问题，而上面的递归代码有很多重复计算的问题，从上面的状态空间树也可以看出：

图中标注的两个子问题其实是一模一样的，只不过上面的会- 提到的已解决的递归代码被一次又一次地解决。

基于此，我们可以添加缓存进行优化：

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

来自 Coder Desert Island Survival，作者 Desert Island Survival of Coders