動態規劃：任務規劃變化

Question

我正在努力解決動態規劃問題幾天。它是這樣的： 約翰的工作日被劃分爲N個時隙，每個時隙我都有一個他可以接收的增益G [i]，他在那個時隙中工作。如果他決定在時間間隔[i，j]工作，那麼他的總獎勵將是R [i，j] = G [i + 1] + ... + G [j]，因爲第一個時間段用於預熱。每天他必須準確地工作T個時隙 - 他可以從可用的N個總時隙中選擇T個時隙的一個子集。他希望通過選擇一組不相交區間[a1，b1]，[a2，b2]，... [ak， < ak < = bk和Sum [i = 1，k]（bi-ai + 1）= T。例如：N = 7，T = 5，增益矢量{3,9,1,1,7,5,4}。最佳解決方案是選擇間隔[1,2]和[4,6]，總利潤爲9 + 12 = 21。

Answer 1

DP解決方案： int f [i] [j] [0..1];

let f[i][j][0] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is not used. 
let f[i][j][1] denotes the maximal gain for the first i time slots and using j time slots, and the i-th time slot is used. 

obviously,f[i][j][k] can determine f[i+1][j][k] or f[i+1][j+1][k]. details below: 
f[i+1][j+1][1]=max(f[i+1][j+1][1],f[i][j][0],f[i][j][1]+G[i+1]); 
f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0],f[i][j][1]);