Curs 5. Programare Dinamica 1

mod = 66793
for(int i = 1; i <= n; ++i) {
  cin >> x;
  long long prod = 1;
  for(int j = 1; j <= x; ++j)
    prod = (1LL * prod*j)%mod;
}
cout << prod;

O(N^2) N*X

1. Definitia
Fact[i] = factorialul pana la i ( Rezolvarea problemei pana in punctul i)
2. Recurenta
Fact[i] = (1LL * Fact[i-1] * i ) % mod (  formulele/recurenta se exprima in functie de elemnte deja calculate)
3. Intializare
Fact[0] = 1;
4. Raspunsul:
Fact[x]


#include <iostream>
using namesapce std;
const int XMAX = 1e6 + 5;
int Fact[XMAX];
int main() {
//Intiliaziarea Fact[0] = 1;
//recurenta  for(int i = 1; i <= XMAX; ++i)
    Fact[i] = (1LL * Fact[i-1] * i ) % mod;
    
  for(int i = 1; i<= n; ++i) {
    cin >> x;
    cout << Fact[x] << "\n";
  }
}
O(N + XMAX);

Enunț:
 2. Se dă un vector de numere pozitive a[1..n]. Alege elemente astfel încât să nu fie două alăturate și suma lor să fie maximă.
 2 7 6  => 8 6 + 2

1. Defintia
dp[i] = suma maxima pana la pozitia i, astfel incat  sa nu fie doua valori alaturate.
2. Recurenta
dp[i] = max(a[i] + dp[i-2], 0 + dp[i-1]);

3. Intializare
dp[0] = 0;
dp[1] = a[1];
4. Raspunsul
dp[n];
#include <iostream>
using namesapce std;
const int NMAX = 1e6 + 5;
int dp[XMAX];
int main() {
//Intiliaziarea 
dp[0] = 0;
dp[1] = a[1];
//recurenta  
for(int i = 2; i <= NMAX; ++i)
    dp[i] = max(a[i] + dp[i-2], 0 + dp[i-1]);
//RASPUNSUL
    cout << dp[n];
}

1. Definitia
dp[i][j] = numarul de posiblitati pana in punctul i,j
2. Recurenta
dp[i][j] = dp[i-1][j] + dp[i][j-1];
3. Intializarea
dp[0][1..m] = 1;
dp[1..n][0] = 1;
4.Raspunsul
dp[n][m];
#include <iostream>
using namesapce std;
const int NMAX = 1e3 + 5,MMAX = 1e3+5;
int dp[NMAX][MMAX];
int main() {
//Intiliaziarea 
for(int i = 1; i <= m; ++i)
  dp[0][i]=1;
for(int i = 1; i <= n; ++i)
  dp[i][0]=1;
cin >> n >> m;
//recurenta  
for(int i =1; i <= n; ++i)
foR(int j = 1; j <= m; ++j)
    dp[i][j] = dp[i-1][j] + dp[i][j-1];
//RASPUNSUL
    cout << dp[n][m];
}

1.  Defintie
dp[i] = cate moduri pot sa ajung la treapta i;
2. Recurenta
dp[i] = dp[i-1] + dp[i-2] ...  + dp[i-k];
3.  Intializarea
dp[1] = 1;
4. Raspuns:
dp[n];
#include <iostream>
using namesapce std;
const int NMAX = 1e3 + 5,MMAX = 1e3+5;
int dp[NMAX];
int main() {
cin >> n >> k;
dp[1] = 1;
for(int i = 2; i <= n; ++i)
    if(i-j >0)
      dp[i] = (dp[i] + dp[i-j])%mod;
    else break;
  cout << dp[n];
}
 O(N*K)
 
 

#include <iostream>
using namesapce std;
const int NMAX = 1e3 + 5,MMAX = 1e3+5;
int dp[NMAX], sp[NMAX];
int main() {
cin >> n >> k;
dp[1] = 1;
sp[1] = a[1];
for(int i = 2; i <= n; ++i) {
  dp[i] = sp[i-1] - sp[max(i-k-1,0)] 
  sp[i] = sp[i-1] + dp[i]; 
  }
  cout << dp[n];
}
 

1. DEFINTIE
dp[i][j] = prin metode pot sa ajung la (i,j)

2. Recurenta
dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1];
3. Intializarea
dp[1][1] =1;
for(int i = 2; i <=n; ++i)
  for(int j = 1; j <= i; ++j)
  if(i-1 >0 && j-1 > 0)
    dp[i][j] += dp[i-1][j-1] ;
  if(i-1>0)
  dp[i][j] += dp[i-1][j];
  if(j+1 <=i-1 && i-1 >0)
  dp[i][j]+= dp[i-1][j+1];
Raspuns
for(int i = 1; i <= n; ++i)
  s+= dp[n][i];
cout << s;
  

1. DEFINTIA:
dp[i][j] = numarul minim de dale care trebuie inlocuite ca sa ajung la (i,j)
2. Recurenta:
      i-1,j
i,j-1 (i,j)

if(a[i][j] == 0)
dp[i][j] = min(dp[i-1][j],dp[i][j-1]);l
else
dp[i][j] = min(dp[i-1][j],dp[i][j-1])
INTIALIZAREA:
for(int i = 1; i <= 2; ++i)
  for(int j = 1; j <= n; ++j)
  
    if(a[i][j] == 0)
      dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
    else
      dp[i][j] = min(dp[i-1][j],dp[i][j-1])


RASPUNS:
min(dp[1][n],dp[2][n]);

a) numărul cuvintelor de lungime n formate doar din litere mari și mici și cu proprietatea că aceste cuvinte nu pot avea două litere alăturate identice, indiferent că sunt mari sau mici (cuvintele baArda sau fEEric au două litere alăturate identice).

1. DEFINITIE
dp[i][LIT] = numarul de cuvinte  de lungime i care sa pot forma nu pot avea două litere alăturate identice si ultima litera este LIT
2. RECURENTA
dp[i][LIT] = dp[i-1][a] + dp[i-1][b] +......dp[i-1][A] + .... 
3. Intiliazarea
for(int i = 1;j <= 52;++j)
dp[1][lit] = 1;
  for(int i = 2; i <= n; ++i)
    for(int lit= 1;lit<= 52; ++lit)
        for(int j =1 ;j<= 52; ++j)  
       if(j !== lit && j != lit+26 && j != lit-26)
          dp[i][lit] += dp[i-1][j]

Raspuns:
dp[n][a] + dp[n][b] +....dp[Z]
for(int i = 1; i<= 52 ;++i)
  sol += dp[n][i];
  
  

  DICTIONAR:
  PROGRAMRE DINAMICA: e o metoda care precalculeaza solutii partiale ale problemei
  DEFINITA: este atribuire unui nou sens/scop unui tablou
  RECURENTA: este o formula cu care calculam tabloul ales in defintie. Formula trebuie sa se bazeze pe membrii anteriori si sa ii unifice (adunam, min, max)
  INTIALIZARE: niste valori in tablou la cazuri mici (0,1,2) calculati de mana de noi, ca sa avem suficiente date ca recurenta sa se poata calcula.
  RASPUNS:  este tot o formula a unor valori din tablou incat sa rezulte solutia problemei( de obicei este o combnatie de ulimtele linii sau valorii ale tabloului n,m)
  STARE:  dp[i][j][lit] , starea este (i,j,lit).  De obicei starea este fix o pozitie sau o bucata mai mica de problema. Insa, uneori vrem mai mult control, ca sa putem satisface condtiile problemei, si putem veni cu stari suplimentare pentru a stastiface conditia lit. Cu cat aducem mai multe stari cu atat crestem complexitatea.
  CONDITIE: este o restrictie care trebuie satisfacuta pentru a obtine un raspuns corect: poate sa sara de pe primele k,  nu are voie sa aiba litere vecine egale, nu are voie sa aiba 2 elemente altaturate. Conditiile dicteaza recurentele. Daca condtiile sunt grele de statisfacut atunci ne obliga sa mai intorducem  stari;