可被 n 整除的非连续元素解决方案不起作用

Question

计算给定整数数组可被 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;
}

谁能指出错误？

Answer 1

问题是 "empty" 序列被认为是一个解决方案（m == 0 当您开始呼叫并且不添加任何数字将在最后留下 m == 0）。

要么是正确的，但是 {1, 2, 3, 2} 的解是 4，或者您需要通过回复 fun(0, 0)-1.

来减去它

可被 n 整除的非连续元素解决方案不起作用

Non-contiguous element divisible by n solution not working

algorithm

recursion

memoization

dynamic-programming