Подсчитайте общие последующие последствия, чья сумма делится на k ⇐ JAVA

[Anonymous]

Я пытаюсь написать решение DP для задачи: количество подсчета общее количество подпоследований, возможных из массива, чьи элементы 'сумма делится на k. < /p>

Я написал следующее решение. Но это не дает правильного результата. Как и в следующем фрагменте кода, массив составляет {1, 2, 1} и k = 3. Таким образом, ожидаемое общее количество подпоследовательностей делится на 3 составляет 2, но фактический результат - 3, что явно неверно. < /P>

Пожалуйста, укажите мою ошибку. < /P>

Укажите мою ошибку. < /P>

.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[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);
}


Подробнее здесь: https://stackoverflow.com/questions/327 ... sible-by-k