如何将递归解决方案转换为动态规划(3D-DP)

[ad_1]

昨天我遇到了以下情况 问题 在比赛中:

问题陈述:

给您一个由 ‘N’ 个整数组成的数组 ‘A’,编号从 ‘0’ 到 ‘N – 1’ 以及一个整数 ‘K’。 您必须确定长度大于“1”且连续元素之和可被“K”整除的子序列的计数。

子序列是可以通过删除某些元素而不改变剩余元素的顺序从原始数组派生的数组。

您的任务是告诉长度大于“1”的子序列的数量以及可被“K”整除的连续元素的总和。 由于答案可能非常大,因此返回对“10^9 + 7”取模。

限制条件:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <= 'A[i]' <= 10^9
时间限制:1秒

我尝试过的:

我的代码:

int mod = 1e9+7;
long long solve(vector <int> &a,int k,int i,int l,int last){
    if(i==0){
        if(l>1) return 1;
        else return 0;
    }
    else{
        if(last==-1 || ((a[last-1]+a[i-1])%k==0)){
            return(solve(a,k,i-1,l+1,i)%mod + solve(a,k,i-1,l,last)%mod)%mod;
        }else{
            return solve(a,k,i-1,l,last)%mod;
        }
    }
}
long long kDivsibleSubsequences(int n, int k, vector <int> &a){
    return solve(a,k,n,0,-1)%mod;
}

l = 当前子序列的长度。
最后 = 我们从向量中选取的最后一个元素

我想到了一个带有记忆功能的递归解决方案以进一步优化,但是在我编写代码后,我在递归中遇到了 3 个不断变化的变量(i,l,last),这意味着 3-D dp 这是不可能的,因为限制。

由于我是 DP 的初学者,在这么短的时间内直接提出自下而上的方法对我来说是不可行的,有人可以让我知道是否有办法记住这些问题,或者我必须来吗采用自下而上的解决方案。

PS-提前致谢:)

[ad_2]

コメント

标题和URL已复制