Что такое эффективный способ подсчета числа непересекающихся подпоследовательностей заданного массива целых чисел, делящихся на n? А = {1,2,3,2} п = 6 Выхода потому, что 12, 12, 132, делится на 6Несмежный элемент, делящийся на n решение не работает
моего решения, которое использует динамическое программирование дает мне неправильный результат. Это всегда дает мне больше, чем фактический результат.
#include <stdio.h>
#define MAXLEN 100
#define MAXN 100
int len = 1,ar[] = {1, 6, 2},dp[MAXLEN][MAXN],n=6;
int fun(int idx,int m)
{
if (idx >= (sizeof(ar)/sizeof(ar[0])))
return m == 0;
if(dp[idx][m]!=-1)
return dp[idx][m];
int ans=fun(idx+1,m); // skip this element in current sub-sequence
ans+=fun(idx+1,(m*10+ar[idx])%n); // Include this element. Find the new modulo by 'n' and pass it recursively
return dp[idx][m]=ans;
}
int main()
{
memset(dp, -1, sizeof(dp));
printf("%d\n",fun(0, 0)); // initially we begin by considering array of length 1 i.e. upto index 0
return 0;
}
Может кто-нибудь указать на ошибку?