كيفية تحويل الحل العودي إلى البرمجة الديناميكية (3D-DP)

بالأمس جئت عبر ما يلي سؤال في مسابقة:

عرض المشكلة:

يتم منحك مصفوفة “A” من أعداد صحيحة “N” مرقمة من “0” إلى “N – 1” وعدد صحيح واحد “K”. يجب عليك تحديد عدد التتابعات التي يكون طولها أكبر من “1”، ويكون مجموع العناصر المتتالية قابلاً للقسمة على “K”.

اللاحقة هي مصفوفة يمكن اشتقاقها من المصفوفة الأصلية عن طريق حذف بعض العناصر دون تغيير ترتيب العناصر المتبقية.

مهمتك هي معرفة عدد التتابعات التي يزيد طولها عن “1” ومجموع العناصر المتتالية القابلة للقسمة على “K”. نظرًا لأن الإجابة قد تكون كبيرة جدًا، قم بإعادتها إلى “10^9 + 7”.

قيود:
1 <= 'ت' <= 10
1 <= 'ن' <= 10^5
1 <= 'ك' <= 10^9
1 <= 'أ[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;
}

ل = طول التسلسل الحالي.
last = العنصر الأخير الذي اخترناه من المتجه

لقد فكرت في حل عودي مع الحفظ لمزيد من التحسين، ولكن بعد أن كتبت الكود الخاص بي، كنت عالقًا مع 3 متغيرات متغيرة (i,l,last) في التكرار مما يعني dp ثلاثي الأبعاد وهو ما لم يكن ممكنًا بسبب قيود.

نظرًا لأنني مبتدئ في DP، فإن التوصل مباشرةً إلى نهج تصاعدي ليس ممكنًا بالنسبة لي في مثل هذا الوقت القصير، هل يمكن لأي شخص أن يخبرني إذا كانت هناك طريقة لحفظ مثل هذه الأسئلة أو هل سيتعين علي الحضور مع حل من أسفل إلى أعلى.

ملاحظة: شكرًا مقدمًا 🙂