La dieta di poldo(dinamica)

Aiuto
1

Qualcuno mi sa dire dove sbaglio?
Il risultato che mi da il mio compilatore è : segmentation fault core dumped.
Ecco qui il codice:

 #include <iostream>
 #include <fstream>
 #define MAX 10000
 using namespace std;


int memo[MAX][MAX];
int calcola(int p[],int n,int prec,int i)
{
    if(i >=n) return 0;
    if(memo[prec][i] != -1) return memo[prec][i];
    int preso = 0,noPreso;
    if(p[i] < prec) preso = 1+calcola(p,n,p[i],i+1);
    noPreso = calcola(p,n,prec,i+1);
    if(preso>noPreso)
    {
        memo[prec][i] = preso;
        return preso;
    }
    else
    {
        memo[prec][i] = noPreso;
        return noPreso;
    }

}
int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");

    int N, panini[MAX];
    cin>>N;
    for(int i = 0;i<N;i++)  cin>>panini[i];
    for(int i = 0;i<MAX;i++)
    {
        for(int j = 0;j<MAX;j++)
        {
            memo[i][j] = -1;
        }
    }
    cout<<calcola(panini,N,MAX+10,0);
    return 0;
}
2

Nel codice dichiari in e out, per poi utilizzare invece cin / cout.
Inoltre passando MAX+10 come valore di prec alla prima chiamata, accedi a un’indice non valido della matrice memo :slight_smile:

Inoltre, una matrice di 10^4 * 10^4 = 10^8 interi è troppo grande per i limiti di memoria del problema.
Puoi passare a un approccio bottom up o trovare un modo per memorizzare i dati utilizzando meno memoria

3

Il problema puoi approcciarlo in maniera non ricorsiva e probabilmente ti verrà più semplice :slight_smile: