Comment convertir une solution récursive en programmation dynamique (3D-DP)

Hier, je suis tombé sur ce qui suit question dans un concours :

Énoncé du problème :

Vous recevez un tableau « A » de « N » entiers numérotés de « 0 » à « N – 1 » et un seul entier « K ». Vous devez déterminer le nombre de sous-séquences dont la longueur est supérieure à « 1 » et la somme des éléments consécutifs est divisible par « K ».

Une sous-séquence est un tableau qui peut être dérivé du tableau d’origine en supprimant certains éléments sans modifier l’ordre des éléments restants.

Votre tâche consiste à indiquer le nombre de sous-séquences ayant une longueur supérieure à « 1 » et la somme des éléments consécutifs divisibles par « K ». Puisque la réponse peut être très grande, renvoyez-la modulo ’10^9 + 7′.

Contraintes:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <= 'A[i]' <= 10^9
Limite de temps : 1 seconde

Ce que j’ai essayé :

Mon code :

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 = longueur de la sous-séquence actuelle.
last = dernier élément que nous avons sélectionné dans le vecteur

J’ai pensé à une solution récursive avec mémorisation pour une optimisation ultérieure, mais après avoir écrit mon code, je me suis retrouvé coincé avec 3 variables changeantes (i, l, last) dans la récursivité, ce qui signifie un dp 3D qui n’était pas possible en raison du contraintes.

Comme je suis un débutant en DP, proposer directement une approche ascendante n’est pas réalisable pour moi en si peu de temps, quelqu’un peut-il me faire savoir s’il existe un moyen de mémoriser de telles questions ou devrais-je venir avec une solution ascendante.

PS- Merci d’avance 🙂