动态规划练习

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）是比最后短每一个。对于j = T-1..N-1，期望的答案是max（S（j，T））

令人高兴的是，你可以安排计算，使得最大值是递增计算的，运行时间是O（NT）和空间是O（N）

工作出你的榜样，规划表看起来是这样的：

   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