动态规划练习的递归关系

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

这是一个很好的小问题...如果选择的最后一个槽(最后一个范围的末尾)是i并且在槽0..i之中,则将S(i,t)定义为可能的最大权重.确切地选择了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)是比最后短每一个.期望的答案是max(对于j = T-1..N-1,S(j,T))

很高兴您可以安排计算,以便逐步计算最大值,运行时间为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