動態規劃練習

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