动态规划递推求解

Question

我试图解决加权间隔调度问题。基本上，为了得到最优解的长度，我提出了以下递归方法：

optimum[i] = max(duration(intervals[i]) + opt[prior[i]], opt[i - 1])

其中prior[i]=在当前间隔开始之前完成的最新非重叠计划。在

这种方法效果很好，我得到了正确的解决方案。然而，我不想得到实际的时间表。我怎么能做到呢？我试着从最大的p[I]值开始，跟着指针，直到到达None/-1/Null，但这并不总是有效的。我假设在解决上面的重复问题时，我需要跟踪要保留的间隔和要放弃的间隔。我试着做一些类似的事情：

^{pr2}$

但这并不奏效。在

Answer 1

您可以使用prior[i]和optimum[i]来构造路径。具体地说，从i开始，得到最优解。然后可以得到如下路径。在

queue<int> path;
int st = i;
while (st > 0) {
  if (op[st] == op[st-1]) st = st -1;
  else {
    path.push(st);
    st = prior[st];
  }
}
pop each item from queue<int> path, you get the intervals you selected.