找到n個元素的最大總和的陣列，使得不超過k個元素是相鄰

Question

幾乎與此相同： find maximum sum of elements in an array such that not more than k elements are adjacent

除了有n個元素，我們可以選擇的限制。如何修改DP算法以使其適用於此？

Answer 1

好吧，讓我說清楚一點。

問題：找到n個元素的最大總和的陣列，使得不超過K中的元素是相鄰

讓INT F [i] [j] [k]的表示最大總和爲第i個元素，使用j個總元素並使用最後的k個元素。讓bool g [i] [j] [k]表示是否有可能獲得某種組合。例如。 g [1] [1] [2]是錯誤的。這很重要，因爲沒有限制，f可能會生成不可能答案。

最初，memset f和g全爲零並且設置g [0] [0] [0]爲真。我們可以使用forward recurrence來解決這個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元素，你可以用這種方式進行更改：

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

Answer 2

添加DP功能的新維度： f[i, j, l] - 最大總和第一我元素，如果使用Ĵ總元素和最後L型元件在這個總和。