在我的算法类(class)中，书中有一个问题如下:“给你一个正数数组 a[1..n] 和一个整数 k。你必须生成一个数组 b[1.. .n]，这样:对于每个 j，b[j] 要么是 1 要么是 0。数组 b 最多有 K 次相邻的 1。Sum(a[j]*b[j]) for 1 <= j <= n 最大化。”例如给定数组 [10, 100, 300, 400, 50, 4500, 200, 30, 90] 和 k = 2 数组 b 可以是 = [1, 0, 1, 1, 0, 1, 1, 0 , 1] 使总和达到 5500。
解决方案在与一些 friend 讨论时使用动态规划，他们说递归关系的形式为 M(i, j) = max(M(i-2, j) + a[i], M(i- 1、j-1) + a[i])
有人能解释一下为什么吗？或者他们是否有解决此类问题的不同形式。我发现动态规划有点难以掌握。 谢谢。
最佳答案
M[i, j]是从1到i的最大和，j个相邻的1
M[i,j] 可以计算为 3 种情况中的最大值:
b[i]=0 => S=M[i-1, j] // a[i] not added to sum, b[1..i-1] has same number of adjacent 1s (j) as b[1..i] because b[i] is zero
b[i]=1 and b[i-1]=0 => S=M[i-2, j]+a[i] // a[i] added to sum, b[1..i-2] has same number of adjacencent 1s, because b[i-1] is zero
b[i]=1 and b[i-1]=1 => S=M[i-1, j-1]+a[i] // a[i] added to sum, since b[i] and b[i-1] are both 1, they count as adjacent 1s, so b[1..i-1] contains only j-1 adjacent 1s
递归规则是上述 3 个和中的最大值。 结束条件为M[1, j]=a[1]，因为b[1..1]只有一项b[1]=1且没有相邻的1。
我们需要的答案是 M[n, k]。
复杂度为 O(nk)。
关于arrays - 最多k个相邻的1s(最大值限制邻居)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30823959/