計算其總和可被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整除的子序列總數

回答

相關問題