Ciao @flp_o3,
Non sono la persona più qualificata del mondo nel spigare programmazione dinamica, di conseguenza se cometto qualche imprecisione spero che qualcuno più abile in questo campo possa coreggermi!
Per il resto questo messaggio sarà diviso in tre parti:
-
Nella prima cercherò di spiegarti come mai il tuo codice non funziona e ti farò vedere il codice funzionanente che riprende la tua idea di risoluzione.
-
Nella seconda ti mostrerò la soluzione a mio avviso più semplice per risolvere questo problema nel modo corretto senza uscire dai limiti di tempo.
-
Nella terza invece ci saranno dei piccoli trucchetti e corezzioni di alcuni errori presenti nel tuo codice che spero possano esserti utili in futuro
Prima parte:
L’ide di base è che esiste una fuzione f(k) tale che, quando calcolata, resituisce il valore della sequenza più lunga che si ferma nella posizione k dell’array. Di conseguenza, per trovare la soluzione al problema, è sufficiente iterare su tutti gli elementi dell’array per trovare la sequenza più lunga in generale. Cioe:
soluzione = \max_{\substack{k = 0 \dots N - 1}} \left(f(k)\right)
L’idea alla base è giusta, il problema è che la tua implementazione è errata! Il main in generale è abbastanza corretto, ma la funzione function che definisci a riga 33 è sbagliata. Infatti con il for a riga 39 stai richiamando la funzione ricorsivamente, ma su dei valori che dovrebbe calcolare dopo. Infatti la funzione non può calcolare le sequenze maggiori che partono da numeri più avanti di k se non ha un modo di recuperare quelle che partono da numeri minori. Inoltre manca un caso base per fare in modo che la ricorsione funzioni.
Vediamo come si risolve questo problema ricorsivamente seguengo l’idea indicata sopra:
La nostra funzione f(k) ci restituisce il valore della sequenza più lunga che termina alla posizione k dell’array. Il caso base in questo caso è f(0) = 1 in quanto se ho un solo elemento l’unica sequenza che posso formare è lunga 1. Per risolvere il problema allora definisco ricorsivamente la funzione in modo tale da poterla costruire da valori “più piccoli” di k: f(k) = \max\left(1, \max_{\substack{i = 0 \dots k-1 \\ v[i] < v[k]}} \left(f(i)\right) + 1\right)
In pratica cosa significa la formulona che ho scritto sopra? Che se voglio sapere qual’è la sequenza più lunga che termina in k io devo controllare tutte le sequenze che finisco in posizioni minori di k (i = 0 \dots k-1) che posso prendere (v[i] < v[k]), e ovviamente prendere la maggiore, sommandoci
1 essendo l’elemento k compreso nella sequenza che voglio calcolare.
Un esempio di codice che implementa questa soluzione:
Soluzione 1
#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int f(int k) {
if(k == 0)
return 1;
int sol = 1;
for(int i = k - 1; i >= 0; i--) {
if(v[i] > v[k])
sol = max(sol, f(i) + 1);
}
return sol;
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//lettura inputs
int n;
cin >> n;
int temp;
for(int i = 0; i < n; i++) {
cin >> temp;
v.push_back(temp);
}
//calcolo della soluzione
int sol = 1;
for(int i = 0; i < n; i++)
sol = max(sol, f(i));
cout << sol;
return 0;
}
Se provi a sottomettere questa soluzione però noterai che il punteggio sarà solo di 35/100, in quanto la ricorsione è troppo lenta. La complessità risulta infatti \mathcal O(2^N) (grazie a @MyK_00L). Vediamo come ottimizzarla!
Seconda parte:
Qui entra in gioco la programmazione dinamica! Infatti l’idea della DP (che è la sigla per dynamic programming) sta nel memorizzare i risultati calcolati in modo da non calcolarli vuovamente. Se ci si fa caso infatti, per ogni valore di k, quando si calcola f(k) si ricalcolano da capo tutti i valori di f(h) dove h < k. Basterebbe quindi memorizzare in un vettore i valori di f(k) già calcolati in modo da non rifarlo tutte le volte. Una soluzione potrebbe essere la seguente:
Soluzione 2
#include <bits/stdc++.h>
using namespace std;
vector<int> v, valori;
vector<bool> calculated;
int f(int k) {
if(k == 0)
return 1;
if(calculated[k])
return valori[k];
calculated[k] = true;
for(int i = k - 1; i >= 0; i--) {
if(v[i] > v[k])
valori[k] = max(valori[k], f(i) + 1);
}
return valori[k];
}
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//lettura inputs
int n;
cin >> n;
int temp;
for(int i = 0; i < n; i++) {
cin >> temp;
v.push_back(temp);
valori.push_back(1);
calculated.push_back(false);
}
//calcolo della soluzione
int res = 1;
for(int i = 0; i < n; i++)
res = max(res, f(i));
cout << res;
return 0;
}
L’array valori serve per memorizzare i valori di f(k) in modo da non ricalcolarli tutte le volte, e lo si inizializza a 1 in quanto ogni sequenza è formata da almeno un elemento. Inoltre l’array calculated è un vettore di booleane (cioè ogni cella dell’array può assumere solo due valori, vero o falso) che tiene traccia dei valori già calcolati. Dentro la funzione f bisogna solo controllare, prima di inziare a fare tutti i calcoli, che il valore cercato non sia già stato calcolato in precedeza (if(calculated[k])), e in caso positivo si returni semplicmente il valore (return valori[k]).
Con questi accorgimenti si arriva ad un 100/100 e ad una complessità di \mathcal O(N^2), quindi il problema potrebbe essere finito qui…e invece no!
Infatti molti problemi di DP sono facili da pensare ricorsivamente, ma più veloci e più comodi da implementare iterativamente. Ti lascio di seguito la soluzione senza l’utilizzo della ricorsione, se hai qualche dubbio scrivi pure che ti spiego come funziona, perché ti sarà sicuramente utile per problemi futuri!
Soluzione 3
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
vector<int> v(N);
for(int i = 0; i < N; i++) cin >> v[i];
vector<int> sol(N, 1);
for(int j = 1; j < N; j++) {
for(int i = 0; i < j; i++) {
if(v[j] < v[i])
sol[j] = max(sol[j], sol[i] + 1);
}
}
cout << *max_element(sol.begin(), sol.end());
return 0;
}
Esistono soluzioni ancora più effcienti che hanno complessità \mathcal O(NlogN). Ma sono assolutamente esagerate per questo problema.
Terza parte:
Siamo finalmente giunti alla parte conclusiva di questo lunghissimo messaggio dove ti lascio alcuni suggerimenti e trucchi che ti potrebbero essere utili in generale per scrivere codice più veloce ed efficiente:
-
Al posto di includere tante librerie diverse scrivi semplicemente #include <bits/stdc++.h> e hai tutto quello che ti serve
-
La funzione max è già implementata in C++, non ti serve scriverla tutte le volte da capo
-
Chiamare una funzione function non è il massimo, in quanto il nome risulta ambiguo ad alcuni editor e compilatori. Dai nomi brevi, significativi e poco ambigui
-
Generalmente avere variabili globali che si modificano dentro a funzioni ricorsive è molto rischioso, cioè devi essere molto bravo e sapere costa stai facendo per usarle bene (la tua variabile contatore). Io personalmente ti sconsiglio di usarle se sei alle prime armi
-
Attento alle dichiarazioni dei for. Nella tua funzione function dichiari i = k + 1, ma se poi chiami la tua funzione con il parametro k = n - 1, i diventerà uguale ad n e si andranno a fare dei casini con gli indici dei vettori
-
Quando prendi in input un vettore un usare push_back. Infatti anche se sulla wiki c’è scritto che ha un tempo costante non è proprio vero, ed è abbastanza lento qando i numeri diventano tanti. Piuttosto dichiara inizialmente la grandezza del vettore (tanto la sai sempre visto che hai N) e successivamente utilizza un semplice cin >> v[i]. Se il vettore è globale e si dichiara prima che tu prenda in input N, allora puoi semplicemente ridimensionarlo appena hai il numero di elementi che contiene con v.resize(N).
Come suggerisce @MyK_00L puoi anche scrivere for(int &i:v)cin>>i. Vedi te cosa preferisci
-
Se aggiungi queste tre istruzioni al tuo programma prenderà gli input più velocemente: ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
-
È inutile ri-inizializzare una variabile a zero se poi la prendi in input (riga 87 del tuo programma).
-
Evita di utilizzare così tanti spazi tra un’istruzione e un altra, rende il codice molto dispersivo e difficile da leggere
Per il resto dovrei averti detto tutto quello che potevo. Se hai qualche domanda falla pure senza problemi (soprattuto se non hai capito qualcosa della spiegazione).