पुनरावर्ती समाधान को गतिशील प्रोग्रामिंग (3D-DP) में कैसे परिवर्तित करें

कल मुझे निम्नलिखित जानकारी मिली सवाल एक प्रतियोगिता में:

समस्या का विवरण:

आपको ‘0’ से ‘एन – 1’ तक क्रमांकित ‘एन’ पूर्णांकों की एक सरणी ‘ए’ और एक पूर्णांक ‘के’ दिया गया है। आपको उन अनुवर्ती अनुक्रमों की गिनती निर्धारित करनी होगी जहां लंबाई ‘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;
}

एल = वर्तमान अनुवर्ती की लंबाई।
अंतिम = अंतिम तत्व जिसे हमने वेक्टर से चुना है

मैंने आगे अनुकूलन के लिए मेमोइज़ेशन के साथ एक पुनरावर्ती समाधान के बारे में सोचा, लेकिन अपना कोड लिखने के बाद मैं पुनरावर्तन में 3 बदलते चर (आई, एल, लास्ट) के साथ फंस गया था जिसका अर्थ है 3-डी डीपी जो कि संभव नहीं था प्रतिबंध।

चूंकि मैं डीपी में नौसिखिया हूं, इसलिए इतने कम समय में सीधे बॉटम-अप दृष्टिकोण के साथ आना मेरे लिए संभव नहीं है, क्या कोई मुझे बता सकता है कि क्या ऐसे प्रश्नों को याद करने का कोई तरीका है या क्या मुझे आना होगा बॉटम-अप समाधान के साथ ऊपर।

पुनश्च- अग्रिम धन्यवाद 🙂