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

我正在尝试为该问题编写一个DP解决方案：count其元素总和可被k整除的数组的子序列总数。计算其总和可被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); 
}

来源

2015-09-25 coderx

两个基本点：1.当你写一个程序，它不工作，我建议你补充一点，说明它在做什么的打印输出：该功能已输入的状态条件等等。你的问题是“请调试我的代码”。 2.如果您以特定的语言在SO中发布代码，则可以考虑将其添加到问题的标记中。 –

让s表示具有长度N输入序列，并K是给定的除数。

dp[i][j] =序列s[0..i]的子序列的数量，余数等于j。我们将计算所有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]

来源

2015-09-25 09:19:37 piotrekg2

该算法没有给出正确的答案。例如：K = 5。Array：int [] s = {2,3,5,8};可以被K = 5整除的子序列是：（2,3），（2,8），（5），（2,5,8），（2,3,5）。所以总共有5个子序列的总和可以被k = 5整除。但根据你的算法，答案是6.请检查它。 – coderx

空序列总和为0.这就是为什么结果是6. – piotrekg2

在这种情况下结果是否需要包含空序列？ – coderx

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

回答

相关问题