大家好，我是小风哥。休息了将近一个星期，终于满血复活了。下一章再说阳康的故事。今天我要讲的是技术。这是关于动态规划主题的第二篇文章。这篇文章的标题是最赚钱的兼职。假设你是赚钱高手，周末搬砖想兼职。现在有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的解)现在您应该能够看到原始问题和子问题之间的联系。其实这张图的状态空间树还可以继续画，但是因为树太大了，我们只能从上图的第一个选项继续画。那么它的状态空间树就是：当所有的作业都被选中后，就会到达叶节点。这时候我们就可以计算出从根节点到当前叶子节点的整条路径的选择所能得到的奖励总和。从上图我们可以看到最大的reward是150，现在你应该清楚我们是如何一步步把问题分解成更小的子问题，然后用子问题的解得到原问题的解了吧问题。自上而下的递归代码上图中每个方框都是一个子问题，决定因素是当前需要选择哪个工作，假设我们要选择第i个工作，那么我们可以定义问题：int作业调度（inti）；这个函数的意思是从第i个工作到最后一个工作中选择能得到的最大奖励。基于上面的讨论和状态空间树，可以很容易的写出这样的递归代码：vector
