Cara mengonversi solusi rekursif ke pemrograman dinamis (3D-DP)

Kemarin saya menemukan yang berikut ini pertanyaan dalam sebuah kontes:

Pernyataan masalah:

Anda diberikan array ‘A’ berisi bilangan bulat ‘N’ yang diberi nomor dari ‘0’ hingga ‘N – 1’ dan satu bilangan bulat ‘K’. Anda harus menentukan jumlah barisan yang panjangnya lebih besar dari ‘1’, dan jumlah elemen berurutannya habis dibagi ‘K’.

Urutan adalah larik yang dapat diturunkan dari larik asli dengan menghapus beberapa elemen tanpa mengubah urutan elemen lainnya.

Tugas Anda adalah menentukan banyaknya barisan yang panjangnya lebih besar dari ‘1’ dan jumlah elemen berurutan yang habis dibagi ‘K’. Karena jawabannya mungkin sangat besar, kembalikan modulo ’10^9 + 7′.

Batasan:
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'K' <= 10^9
1 <= 'SEBUAH[i]' <= 10^9
Batas Waktu: 1 detik

Apa yang saya coba:

Kode Saya:

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 = panjang barisan saat ini.
last = elemen terakhir yang kita ambil dari vektor

Saya memikirkan solusi rekursif dengan memoisasi untuk optimasi lebih lanjut, tetapi setelah saya menulis kode saya terjebak dengan 3 variabel yang berubah (i,l,last) dalam rekursi yang berarti dp 3-D yang tidak mungkin dilakukan karena kendala.

Karena saya seorang pemula di DP, mengajukan pendekatan bottom-up secara langsung tidak mungkin bagi saya dalam waktu sesingkat itu, dapatkah seseorang tolong beri tahu saya jika ada cara untuk mengingat pertanyaan seperti itu atau apakah saya harus datang dengan solusi bottom-up.

PS- Terima kasih sebelumnya 🙂