Salve, provando a risolvere in modo ricorsivo il problema e ho riscontrato grande difficoltà nella memoizzazione e non ho idea di come utilizzarla nel modo corretto, avete consigli? Per quando riguarda la logica della ricorsione credo sia corretta in quanto senza memoizzazione i primi 7 case li da comunque corretti, ma vi chiedo di dargli uno sguardo in quanto mi sto approcciando da poco alla dp. Grazie in anticipo.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
const int MAXM = 1000;
vector<vector<int> > memo(MAXN+1,vector<int> (MAXM+1,-1));
int solve(int guida,int turista,vector<int> &V, vector<int> &G) {
if(guida==0) return turista;
if(turista==0) return 0;
if(memo[turista][guida]==-1){
if(G[guida-1]>V[turista-1]){
memo[turista][guida] = max(solve(guida-1,turista,V,G),
max(solve(guida,turista-1,V,G)+1,
solve(guida-1,turista-1,V,G)+2));
}else{
memo[turista][guida] = max(solve(guida-1,turista,V,G),
solve(guida,turista-1,V,G)+1);
}
}
return memo[turista][guida];
}