我有个问题要解决。我有n个项目，每一个项目的值v放在一行。然后我有k个监督项目，x位置的一个监督项目可以监督项目x-1，x，x+1。我想计算的是K监督者可以使用动态编程监督的最大值。
如。
n={1,2,3,4}
V={7,10,5,8}
这意味着1->17号位置的主管的总价值（n=1&2可以包括在内）。
位置2->22（N=1,2,3可覆盖）。
位置3->23（N=2,3,4可覆盖）。
位置4->19（n=3,4可覆盖）。
那么，如何计算给定监督员可以覆盖的最大值呢？
在这个例子中，用1个监督器得到最大值23，2得到36（挑选1和4）。
在那之后，我们做不到更好，因为所有的项目都包括在内。
我试过利用背包问题，但后来我陷入了如何解决覆盖重叠的困境。
我也尝试过使用加权区间调度问题，但它只适用于计算可能的最大值，而不是k个区间的最大值。
我非常感谢你能给我任何关于如何用动态编程解决这个问题的建议。
最佳答案
对于1＜i＝i＝n和0＜j＜＝k，将dp[i] [j]定义为当j监视器可以设置时在{ 1…i}中具有索引的监督项的最大值。则dp[i+1][j+1]=最大值（a，b，c），其中
a=dp[i][j+1]//这包括最后一个主管在i-1或eariler时的所有情况
B=DP[I-2][J]+VAL（I-1）+VAL（I）+VAL（I+1）//在I设置主管
C=DP[i-1][j]+val（i）+val（i+1）//将主管安排在i+1
这就得到了O（n*k）