Dp Top-down Best configuration

Sto provando a risolvere problemi con la programmazione dinamica, nello specifico usando la top down e mi chiedevo se con questa tecnica fosse possibile ottenere la configurazione ottimale che mi ha portato al risultato.
Un problema che sto analizzando è questo : data una matrice di dimensioni N*N ,inziando dalla posizione 0,0 e potendosi solo muoversi in basso o a destra, qual è la somma maggiore ottenibile arrivando al ultima cella della matrice.
Ho ideato il seguente codice :
#include <bits/stdc++.h>

using namespace std;

int mat[200][200];
int memo[200][200];
int n;
int solve (int i,int j, int costo){
	if(i == n && j == n)return costo;
	if(memo[i][j]!=-1)return memo[i][j];
	if(i == n){
		while(j<n){
			costo+=mat[i][j];
			j++;
		}
		return memo[i][j]=costo;
	}
	if(j == n){
		while(i<n){
			costo+=mat[i][j];
			i++;
		}
		return memo[i][j]=costo;
	}
	return memo[i][j]=max( solve( i+1,j, costo + mat[i+1][j]) , solve(i, j+1, costo + mat [i][j+1])  )  ;
}
int main(){
	srand(time(NULL));
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			mat[i][j]=rand()%2;
			cout<<mat[i][j]<<" ";
		}
		cout<<"\n";
	}
	memset(memo,-1,sizeof(memo));
	cout<<solve(0,0,mat[0][0]);
}

Avendo trovato la traccia su internet non ho casi di test su cui testarlo per questo faccio generare randomicamente i valori. Ho cercato sul cms col tag dp e non ho trovato un problema simle, se è presente potreste dirmi il nome?
Edit : il codice non funziona devo rivederlo.

Ciao, non credo ci siano problemi identici sulla piattaforma, comunque ci sono problemi simili che possono essere riadattati. Consideriamo ad esempio il problema triangolo, chiamiamo la matrice in input A. Adesso definiamo la matrice B come:

B_{i,j}= \begin{cases} A_{i+j,j} & \text{se } i+j<n\\ 0 & \text{se } i+j\ge n\end{cases} \quad \forall\ i,j\in \{0,1,\ldots ,n-1\}

Per chiarirci meglio questa è la matrice nell’esempio:

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Da questa matrice se ne otterrebbe una come quella seguente:

7 8 0 4 5
3 1 4 6 0
8 7 2 0 0
2 5 0 0 0
4 0 0 0 0

Fatto ciò puoi applicare la soluzione descritta da te sulla matrice appena creata.
Comunque, cosa intendi con “configurazione ottimale”?

2 Mi Piace

Il problema del triangolo l ho risolto senza dp. Ho creato una matrice di n dimesioni e partendo dal basso prendendo una coppia di valori andavo a sommare con l elmento più in alto il numero che mi restituva la somma più alta.
Considerando il triangolo

Diventava

30
23 21
20 13 10
7 12 10 10
4 5 2 6 5

Il quesito che avevo posto sul mio problema è che la top down che ho realizzato mi restituisce la somma ma se volessi sapere quale sequenza di numeri ha sommato per ottenerla?

Quello che ho spiegato prima era semplicemente un modo di verificare la correttezza del codice scritto da te, utilizzando il correttore della piattaforma. Anche io ho risolto quel problema in modo diverso da ciò che ho descritto, tuttavia, dato che avevi chiesto se vi era un problema simile sulla piattaforma, ti consiglio di adattare il tuo codice a quel problema in modo da vedere se effettivamente la parte che calcola il risultato ottimale funziona correttamente :wink: (comunque anche se non sembra, la soluzione che avevi adottato sfrutta il concetto di programmazione dinamica, poi forse intendevi "di dimensioni n\times n" e non “di n-dimensioni”).
Per quanto riguarda il problema di come determinare la sequenza, è relativamente semplice in quanto basta, una volta trovato il risultato ottimale ricostruire il percorso sulla base dei dati appena calcolati. Partendo dalla fine mi muovo verso il nodo sopra o a sinistra con la somma parziale più alta e alle fine stampo il percorso al contrario. Ciò richiedere \Theta (N) spazio, in quanto ti devi salvare il percorso per poterlo stampare in ordine, tuttavia se vedi il problema in modo diverso, ovvero trovare il percorso che parte dall’angolo in basso a destra e arriva nell’angolo in alto a sinistra, puoi evitare di salvarti il percorso e stamparlo direttamente in ordine. Ti lascio un pezzo di codice che ho appena scritto, per comodità l’ho risolto in bottom-up, ma puoi adattarlo facilmente a top-down, il concetto è sempre quello:

dp[N-1][N-1]=mat[N-1][N-1];
for(int i=N-2; i>=0; i--)
{
    dp[N-1][i]=dp[N-1][i+1]+mat[N-1][i];
    dp[i][N-1]=dp[i+1][N-1]+mat[i][N-1];
}
for(int i=N-2; i>=0; i--)
    for(int j=N-2; j>=0; j--)
        dp[i][j]=max(dp[i+1][j],dp[i][j+1])+mat[i][j];

for(int i=0; i!=N; i++)
{
    dp[N][i]=INT_MIN;
    dp[i][N]=INT_MIN;
}
int i=0, j=0;
while(i!=N && j!=N)
{
    cout<<mat[i][j]<<' ';
    if(dp[i+1][j]>dp[i][j+1])
        i++;
    else
        j++;
}
2 Mi Piace

In effetti non funziona, devo aggiustarlo xd

Si, mi sono espresso male <.<

Cosi posso fare in questo caso e se volessi tovare la sequenza ottiamle in un problema generico risolto con la top down?
Sinceramente ho ancora molti dubbi su come attuare al meglio la dp, è complicata >.<

In realtà che si usi una tecnica bottom-up oppure top-down non cambia praticamente niente. Ciò di cui abbiamo bisogno è la matrice con le somme parziali che possiamo ottenere in entrambi i modi. Una volta calcolata applichiamo una strategia simile alla soluzione top-down, ovvero partiamo dalla fine e ad ogni nodo scelgo se andare sopra o a sinistra in base a quale abbia la somma maggiore, forse ti è più comprensibile il seguente codice:

deque<pair<int,int>> path{{N-1,N-1}};
int i=N-1, j=N-1;
while(i>0 || j>0)
{
    if(i==0) j--;
    else if(j==0) i--;
    else if(dp[i-1][j]>dp[i][j-1]) i--;
    else j--;
    path.emplace_front(i,j);
}
for(auto& [x,y] : path)
    cout<<mat[x][y]<<' ';
2 Mi Piace