求数组中长度为k、和为s的子序列计数的高效算法

嘿，直接枚举所有长度为k的子序列确实太不高效了——尤其是当n稍微大一点的时候，组合数直接爆炸，根本跑不动。咱们换个思路，用**动态规划（DP）**来解决这个问题，效率能提升好几个数量级！

核心思路是用DP数组记录「选了i个元素、和为j的子序列数量」，遍历数组时逐步更新状态，完全不需要生成任何子序列。

1. DP状态定义 #

我们定义dp[i][j]表示：从数组前m个元素中，选了i个元素，它们的和恰好为j的子序列总数。

初始状态很简单：dp[0][0] = 1（选0个元素、和为0的情况只有1种），其他所有dp[i][j]初始值为0。

2. 状态转移方程 #

对于数组中的每个元素num，我们从后往前更新DP数组（倒序是为了避免同一个元素被重复选取，毕竟子序列不能重复选元素）：

• 先遍历i从k到1（倒序）：因为选i个元素的状态依赖于选i-1个元素的状态，倒序更新不会覆盖还没用到的上一轮状态
• 再遍历j从s到num（倒序）：确保j - num是非负的，避免无效计算

更新公式：

dp[i][j] += dp[i-1][j - num]

直白点解释：如果我们当前选了num这个元素，那么所有「选了i-1个元素、和为j-num」的子序列，都可以加上这个num，变成「选了i个元素、和为j」的子序列，所以把之前的数量加到当前状态里。

3. 实战示例验证 #

拿你给的例子：A=[1,1,2,2,3]，s=4，k=2，一步步看DP数组的变化：

• 初始：dp[0][0] = 1，其余为0
• 处理第一个1：dp[1][1]变成1（选1个元素和为1的子序列有1种）
• 处理第二个1：dp[2][2]变成1（两个1组成的子序列），dp[1][1]变成2（两个单独的1）
• 处理第一个2：dp[1][2]变成1（单独的2），dp[2][3]变成2（1+2的两种组合）
• 处理第二个2：dp[1][2]变成2（两个单独的2），dp[2][4]变成1（两个2组成的子序列）
• 处理3：dp[2][4] += dp[1][1]（也就是2），最终dp[2][4] = 1+2=3，正好对应示例的结果！

4. 空间优化（可选） #

如果k和s比较大，二维数组可能占内存，我们可以用滚动数组优化空间：

• 要么用两个一维数组prev和curr，分别记录上一轮和当前轮的状态
• 要么直接在一维数组上倒序更新，把空间复杂度从O(k*s)降到O(s)，不过逻辑需要更仔细一点，避免状态覆盖。

复杂度对比 #

• 枚举法：时间复杂度O(C(n,k))，n稍大就完全不可行（比如n=50，k=25，组合数是2.25e13，根本算不完）
• DP法：时间复杂度O(n*k*s)，只要k和s不是特别极端（比如k≤20，s≤1000），就算n=1000也能轻松跑完。

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