java - 计算总和可被 k 整除的子序列总数

Question

我正在尝试为这个问题编写一个 DP 解决方案:计算一个数组的元素总和可被 k 整除的子序列总数。

我写了下面的解决方案。但它没有给出正确的结果。如下面的代码片段，数组是{1, 2, 1}，k = 3。所以期望被3整除的子序列总数是2，但实际结果是3，这显然是不正确的。

请指出我的错误。

private int countDP(int[] a, int k)
{
    int L = a.length;

    int[][] DP = new int[L][k];

    for(int i = 0; i < DP.length; i++)
    {
        for(int j = 0; j < DP[0].length; j++)
            DP[i][j] = -1;
    }

    int res = _countDP(a, k, DP, 0, 0);

    return res;
}

private int _countDP(int[] a, int k, int[][] DP, int idx, int m) //Not giving the correct result.
{
    if(idx == a.length)
        return m == 0 ? 1 : 0;

    if(DP[idx][m] != -1)
        return DP[idx][m];

    int ans = 0;

    ans = _countDP(a, k, DP, idx + 1, m);
    ans += _countDP(a, k, DP, idx + 1, (m + a[idx]) % k);

    return DP[idx][m] = ans;
}

public static void main(String[] args)
{
    CountSubnsequences cs = new CountSubnsequences();

    int[] a = {1, 2, 1};
    int k = 3;

    int total1 = cs.countDP(a, k);

    System.out.println("Total numeber of sub sequences: " + total1);
}

Answer 1

让s表示长度为 N 的序列, 和 K是给定的除数。

dp[i][j] = s[0..i] 的子序列数余数等于 j .我们将计算 dp对于所有 0 <= i < N和 0 <= j < K .

dp[i][j] = 0 for all  (i, j)

dp[0][0] += 1
dp[0][s[0] mod K] += 1

for i = 1 .. N - 1
    for j = 0 .. K - 1
        dp[i][j] = dp[i - 1][j]
    for j = 0 .. K - 1
        dp[i][(j + s[i]) mod K] += dp[i - 1][j]

结果是dp[N - 1][0]