Cómo convertir una solución recursiva a programación dinámica (3D-DP)

Ayer me encontré con lo siguiente pregunta en un concurso:

Planteamiento del problema:

Se le proporciona una matriz ‘A’ de ‘N’ números enteros numerados del ‘0’ al ‘N – 1’ y un único número entero ‘K’. Debe determinar el recuento de subsecuencias donde la longitud es mayor que ‘1’ y la suma de elementos consecutivos es divisible por ‘K’.

Una subsecuencia es una matriz que se puede derivar de la matriz original eliminando algunos de los elementos sin cambiar el orden de los elementos restantes.

Su tarea es indicar el número de subsecuencias que tienen una longitud mayor que ‘1’ y la suma de elementos consecutivos divisibles por ‘K’. Dado que la respuesta puede ser muy grande, devuélvala en módulo ’10^9 + 7′.

Restricciones:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <='A[i]' <= 10^9
Límite de tiempo: 1 segundo

Lo que he probado:

Mi código:

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 = longitud de la subsecuencia actual.
last = último elemento que seleccionamos del vector

Pensé en una solución recursiva con memorización para una mayor optimización, pero después de escribir mi código me quedé atrapado con 3 variables cambiantes (i,l,último) en la recursividad, lo que significa un dp 3D que no era posible debido a la restricciones.

Como soy principiante en PD, no me resulta factible adoptar directamente un enfoque de abajo hacia arriba en tan poco tiempo. ¿Puede alguien decirme si hay alguna manera de memorizar esas preguntas o tendré que venir? con una solución ascendente.

PD: gracias de antemano 🙂