满足子集和不被M整除、最多连续跳K个元素的最大和求解

约束梳理 #

给定参数：

• 数组 A = [6,3,2,1,9,10,2,11]，长度记为 n
• 模值 M = 6
• 最大连续跳过元素数 K = 2
  需要满足：

1. 选中元素总和不能被M整除
2. 任意位置连续跳过的元素数量不能超过K
   目标是求符合约束的最大总和

状态定义 #

定义三维DP数组 dp[i][j][r]：

• i 表示已处理完数组前 i 个元素（i 范围：0~n）
• j 表示处理完第i个元素后，末尾连续跳过的元素个数（j 范围：0~K，j=0 代表第i个元素被选中）
• r 表示当前选中元素的总和模M的余数（r 范围：0~M-1）
• 数组存储的值为对应状态下的最大元素总和

初始状态 #

初始时未处理任何元素，总和为0，连续跳过数为0，余数为0，其余状态均设为负无穷（代表不可达）：
dp[0][0][0] = 0

状态转移 #

遍历每个元素（第i个元素对应原数组下标为i-1），对所有合法的前序状态做两种选择：

1. 选中第i个元素
   选中后末尾连续跳过数重置为0，新余数为(前序余数 + A[i-1]) % M，只要前序状态可达就可以转移：

   dp[i][0][(r_prev + A[i-1]) % M] = max(dp[i][0][(r_prev + A[i-1]) % M], dp[i-1][j_prev][r_prev] + A[i-1])
   

   其中 j_prev 可取0、1、2（任意前序连续跳过数都可以接选中操作）

2. 不选第i个元素
   不选的前提是前序连续跳过数小于K（否则会出现连续跳过K+1个元素的违规情况），转移后连续跳过数+1，余数不变：

   dp[i][j_prev + 1][r_prev] = max(dp[i][j_prev + 1][r_prev], dp[i-1][j_prev][r_prev])
   

   其中 j_prev 可取0、1（最多只能连续跳2个，所以前序最多跳1个，加1后刚好是2）

最终结果取值 #

处理完所有n个元素后，取所有余数不等于0的状态的最大值即可：

result = max( dp[n][j][r] for j in 0..K for r in 1..M-1 )

代入题目示例计算得到的结果为34，和给出的最优解一致。

空间优化 #

由于计算第i层状态时仅需要第i-1层的状态，因此可以将三维数组压缩为两个二维数组prev_dp[j][r]和curr_dp[j][r]，空间复杂度从O(nKM)降低为O(K*M)，适合处理长度更大的数组。

内容的提问来源于stack exchange，提问作者Ramasatyanarayana Motukuri