Probleme explicate programare dinamica
Se dă un şir S = (s1, s2, .., sN) de lungime N (1 ≤ N ≤ 1 000). Un subşir
al şirului este de forma: S' = (si1, si2, ..., siK), i1 < i2 < ... < iK . Se cere să se
determine un subşir al şirului S, care este ordonat strict crescător şi care are
lungimea maximă.
Datele de intrare se citesc din fisierul subsir.in, care conţine pe prima linie
numărul N, iar pe linia a doua N numere naturale, despărţite de un spaţiu,
reprezentând elementele şirului. Programul va afişa pe ecran un număr natural,
care reprezintă lungimea maximă a unui subşir crescator, respectiv un subşir
crescător maximal.
Problema in c++:
Se dau două şiruri: A = (a1, a2, .., aM), cu M elemente (1 ≤ M ≤ 1 000), respectiv B = (b1, b2, .., bN) cu N elemente (1 ≤ N ≤ 1 000). Să se găsească cel mai lung subşir care apare atât în şirul A cât şi în şirul B.
Datele de intrare se citesc din fişierul cmlsc.in, care conţine pe prima linie
un număr N, pe linia a doua N numere, pe linia a treia numărul M, apoi pe linia
următoare M numere. Programul va afişa pe ecran un număr, reprezentând
lungimea subşirului comun maximal, respectiv un subşir comun de lungime
maximă
Sirul lui Fibonacci
În acest exemplu, am creat o funcție numită fibonacci, care ia un întreg n ca argument și returnează al n-lea număr Fibonacci. Mai întâi, verificăm dacă n este mai mic sau egal cu 1. Dacă este, returnăm pur și simplu n (deoarece primul și al doilea număr Fibonacci sunt 0 și 1, respectiv).
Dacă n este mai mare decât 1, atunci începem să calculăm numerele Fibonacci folosind programare dinamică. Cream un vector numit memo cu dimensiunea n+1, unde vom memora rezultatele intermediare pentru a evita recalcularile. Initializam memo[0] cu 0 si memo[1] cu 1, deoarece primul și al doilea număr Fibonacci sunt deja
#include <iostream>
using namespace std;
int fibonacci(int n) {
if (n <= 1) {
return n;
}
int memo[n+1];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
memo[i] = memo[i-1] + memo[i-2];
}
return memo[n];
}
int main() {
int n = 10;
cout << "Fibonacci number at position " << n << " is " << fibonacci(n) << endl;
return 0;
}