Несмежный элемент, кратный n решению, не работает

Каков эффективный способ подсчета количества несмежных подпоследовательностей заданного массива целых чисел, делящихся на n? A = {1,2,3,2} n = 6 Выведите 3, потому что 12, 12, 132 делятся на 6

Мое решение, использующее динамическое программирование, дает мне неправильный результат. Это всегда дает мне один больше, чем фактический результат.

#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;
}

Кто-нибудь может указать на ошибку?


recursion algorithm memoization dynamic-programming
person noman pouigt    schedule 29.09.2015    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Проблема в том, что "пустая" последовательность считается решением (m == 0, когда вы начинаете вызов и не добавляете ни одной цифры, вы остаетесь с m == 0 в конце).

Либо это правильно, но тогда решение для {1, 2, 3, 2} равно 4, либо вам нужно вычесть его, просто указав в качестве ответа fun(0, 0)-1.

person 6502    schedule 29.09.2015