动态规划：任务规划变化

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]);