如何用非暴力DP算法统计数组非空整数平均子序列的个数？

当然存在比暴力枚举更高效的动态规划解法，核心思路是将问题转化为统计满足「子序列总和能被其长度整除」的非空子序列数量（平均值为整数等价于总和是长度的整数倍）。

DP状态定义 #

用二维数组 dp[k][r] 表示：

• k：子序列的长度
• r：子序列总和对 k 取模的余数
• 数组值：满足上述条件的子序列个数

初始状态：dp[0][0] = 1（代表空序列，仅作为状态转移的起始基础）

状态转移逻辑 #

遍历数组中的每个元素 x，倒序遍历当前已有的子序列长度 k（从当前最大长度到0，避免重复使用同一个元素构建子序列）：

1. 当 k = 0（空序列）：
   新增长度为1的子序列，总和为 x，任何数对1取模都是0，因此 dp[1][0] += dp[0][0]
2. 当 k > 0：
   对于每个余数 r（0 ≤ r < k），如果 dp[k][r] > 0，则新增长度为 k+1 的子序列，其总和对 k+1 取模的结果为 (r + x) % (k+1)，因此：

   dp[k+1][(r + x) % (k+1)] += dp[k][r]
   

计算最终结果 #

将所有 dp[k][0]（k 从1到数组长度 n）的值相加，就是符合条件的非空子序列总数。

示例验证（数组 {2,6,2}） #

1. 初始状态：dp[0][0] = 1
2. 处理第一个元素2：
   • k=0 → dp[1][0] += 1 → dp[1][0] = 1
3. 处理第二个元素6：
   • 倒序遍历 k=1：dp[2][(0+6)%2] += 1 → dp[2][0] =1
   • k=0 → dp[1][0] +=1 → dp[1][0] =2
4. 处理第三个元素2：
   • 倒序遍历 k=2：dp[3][(0+2)%3] +=1 → dp[3][2] =1（不贡献结果）
   • k=1：dp[2][(0+2)%2] +=2 → dp[2][0] =1+2=3
   • k=0 → dp[1][0] +=1 → dp[1][0] =3
5. 求和：dp[1][0] + dp[2][0] + dp[3][0] =3+3+0=6，与示例结果完全一致。

复杂度分析 #

• 时间复杂度：O(n²)，每个元素需要遍历 O(n) 个长度，每个长度对应 O(k) 个余数，总和为 1+2+...+n = O(n²)
• 空间复杂度：O(n²)，用于存储所有长度和余数对应的子序列计数；若需优化空间，可使用滚动数组或仅保留上一轮的状态，将空间压缩至 O(n)

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