algorithm - 动态规划练习的递归关系

Question

我收到了一份动态规划作业，我需要帮助来找出递推关系。该问题类似于加权区间问题，但它有一些额外的限制:

• 给你一系列 N时隙，每个时隙都具有相同的持续时间。
• 每个时间段 k , 0 <= k < N , 被赋予正权重 W[k] .
• 对于任何时间间隔[i, j]与 i < j , 重量 W[i,j]该间隔是:
  W[i,j] = W[i+1] + W[i+2] + ... + W[j]
  注意权重 W[i]第一个时隙的不计算在内，因此任何长度的间隔1权重为 0 .

给你一个值 T < N并要求准确选择 T时隙使得所选时间间隔的总和最大化。

示例:对于 N = 5 , T = 4和权重 W = (3, 9, 1, 1, 7) , 选择 W[0, 1] = 9和 W[3, 4] = 7将给出最大权重 16 .

Answer 1

这是一个很好的小问题...定义 S(i, t) 为可能的最大权重，如果选择的最后一个槽(最后一个范围的末尾)是 i 并且在槽 0..i 中恰好有 t已选择插槽。

DP 的决定是我们要么将 w[i] 添加到 S(i, t) 中，要么不添加，因为槽位 i-1 被选中，或者没有被选中。所以我们有:

S(i, t) = max ( S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2 )

t-1>i 无意义的情况。因此基本情况是 S(i, 1) = 0，因为 0 <= i < N，并且 DP 表的连续列 (t = 2,...,T) 每一列都比最后一列短。所需的答案是最大值( S(j, T) for j = T-1..N-1 )

令人高兴的是，您可以安排计算，以便增量计算最大值，运行时间为 O(NT)，空间为 O(N)

根据您的示例，DP 表如下所示:

               t = 
         1    2    3    4
       ------------------
i = 0 |  0
    1 |  0    9   
    2 |  0    1   10
    3 |  0    1    9   11
    4 |  0    7    9   16

答案是 max(11, 16) = 16