algorithm - 求数组中 n 个元素的最大总和，使得相邻的元素不超过 k 个

Question

几乎与此相同： 找到数组中元素的最大总和，使得相邻的元素不超过 k

除了我们可以选择的 n 个元素的限制。如何修改 DP 算法以使其适用于此？

Answer 1

添加 DP 函数的新维度： - 前if[i, j, l]个元素的最大总和，如果使用j个总元素和此总和中的最后 l 个元素。

Answer 2

好吧，让我说得更清楚。

问题：求数组中 n 个元素的最大和，使得相邻的元素不超过 K

让int f[i][j][k]表示前 i 个元素的最大总和，使用 j 个总元素并使用最后 k 个元素。let bool g[i][j][k]表示是否可以得到某种组合。例如。g[1][1][2] 是假的。这很重要，因为没有限制， f 可能会产生不可能的答案。

最初，memset f 和 g 都为零，并将 g[0][0][0] 设置为真。我们可以使用前向递归来解决这个DP问题。显然，每次遇到一个数字，你都有两个选择：选择它，或者放弃它。他们给出了递归公式：

f[i][j][k] can infer f[i+1][j+1][k+1], or
f[i][j][k] can infer f[i+1][j][0]

所以，伪代码可以如下：

memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
g[0][0][0]=true;
for (int i=0;i<array.size();i++)
    for (int j=0;j<=n;j++)
        for (int k=0;k<=K;k++) if (g[i][j][k]) {
            f[i+1][j][0]=max(f[i+1][j][0],f[i][j][k]);
            f[i+1][j+1][k+1]=max(f[i+1][j+1][k+1],f[i][j][k]+array[i]);
            g[i+1][j][0]=true;
            g[i+1][j+1][k+1]=true;
        }

最终结果将是：

ans=0;
for (i=0;i<=K;i++)
    ans=max(ans,f[array.size()][n][i]);
return ans;

上面正好给出了 j 个元素。如果你想得到最多 j 个元素，你可以这样改变它：

ans=0;
for (i=0;i<=n;i++)
    for (j=0;j<=K;j++)
        ans=max(ans,f[array.size()][i][j]);
return ans;