java Count总和可被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

面临同样的问题。但最终得到了答案

返回的答案总是比所有可能的子序列多1个。这是因为我们知道0总是一个有效的答案。因此，如果假设您没有从数组中选取任何单个元素，那么sum=0。因此，它认为这是一个有效的答案，并将我们的答案增加1。因此，要得到实际答案，只需将返回值减1

Answer 2

@piotrekg2解决方案的Python代码。 看起来不错

from typing import List


# dp[i][j] = the number of subsequences of length i with remainder equal to j.
def count_subseq(s: List[int],k):
    n = len(s)
    dp = [0]*k
    dp[0] = 1  # i=0, remainder=0, only 1 subseq
    for i in range(1,n+1):
        dp2 = dp.copy()   # copy previous i-length results: results without s[i] in subseq
        for j in range(k):
            dp2[(j+s[i-1])%k] += dp[j]
        dp = dp2
    return dp[0]


if __name__ == '__main__':
    print(count_subseq([2,3,5,8],5))
    print(count_subseq([5,5,5],5))

Answer 3

int fun(int i,int s)
{

    if(i==1){

        if(s-a[i]!=0 && (s-a[i])%k==0)
        return 1;
        else
            return 0;}
    else{
        if((s-a[i])%k==0){
            return 1+fun(i-1,s-a[i])+fun(i-1,s);
        }
        else{
            return fun(i-1,s-a[i])+fun(i-1,s);
        }
    }
}

Answer 4

设s表示长度序列N，且K是给定的除数

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

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]