/*
Algorimi si metode programare
-----------------------------------
[1] metoda backtraking
[2] metoda greedy
[3] metoda divide et impera
-----------------------------------
[4] metoda programarii dinamice

    - 4.1 programare dinamica "inainte"

Descriere :
In general orice enunt de tip PD este un enunt de optim
( se solicita o selectie a unui subset dintr-un set dat astfel incat
   sa fie indeplinit un anumit criteriu )
La o abordare de tip PD se rezolva problema pentru subseturi
ale setului dat indentificand modul de compunere a raspunsurilor
obtinute pe masura ce crestem dimensiunea datelor de intrare
pana la dimensiunea setului precizat in enunt
In cazul in care compunerea se realizeaza pe baza unor rezultate
obtinute la pasii k+1... n spuneam ca avem PD inainte
( pas curent il consideram k pas final - ce ia in calcul ultimul element din
  setul dat il consideram n )
Altfel spus pana la obtinerea raspunsului la problema formulata
se executa un sir de prelucrari ale datelor de intrare pentru a
obtine datele de iesire. In timp acestor prelucrari datele trec
in urma unor decizii prin diferite stari

datele de intrare=S1 --> S2 -->  ....--> Sk --> .....-> Sn= datele de iesire
                                   D1       D2        Dk    Dk+1     Dn-1

                    Daca forma datelor in starea Sk depinde
                    ( compunere ) de formele datelor din starile Sk+1 ... Sn
                    avem :
                    PD inainte ( programare dinamica cazul inainte )
Caz clasic ( PD inainte )
Problema celui mai lung subsir crescator care se poate forma
luand de pe locuri in ordine valori dintr-un sir dat
exemplu :
n=8 M={6,3,2,7,23,7,32,3}
lungime maxima in conditiile din enunt este 4
S1={2,7,23,32}
S2={3,7,7,32}
S3={6,7,23,32}
S4={3,7,23,32}
S5={2,7,7,32}
S6={6,7,7,32}
lungimea maxima a unei solutii este 4
La orice abordare de tip PD este necesara o structura auxiliara
ce memoreaza raspunsurile starilor deja parcurse
Pentru problema subsir crescator de lungime maxima
utilizez un vector

L[i]= lugimea cel mai lung subsir care se poate forma incepand
         cu elementul i din sirul dat
initial L[n]=1;
rezolvarea presupune completarea continutului lui L
si apoi cautarea maximului in interiorul L.

completarea o execut pentru locuri n-1 .... 1 astfel :

L[i]=1+max { L[j]/ V[j]>=V[i] }

Deci :
1. orice PD utilizeaza o structura auxiliara ( vector, matrice )
2. in structura auxliara aleasa execut o initializare
3. in functie de modul de completare a structurii
    avem :
    - PD inainte ( subsir crescator de lungime maxima )
    - PD inapoi  ( problema numarului Fibonacci  )

           |   x  daca x=0
  F(x)=|  1  daca x=1
           | F(x-2)+F(X-1) daca x>1

0 1 1 2 3 5 8 13 ...

Cerinta  :
Pentru x dat sa se calculeze valoarea F(x)

La o abordare de tip PD utilizez ca structura auxiliara un vector
in care memorez toate raspusurile la problemele formulate
initializez V
V[0]=0
V[1]=1
index curent=2 , pentru toti indecsii pana la valoarea lui x

completez valoare curenta in V invocand valori deja calculate
de pe pozitii precedente  astfel

V[k]=V[k-1]+V[k-2]

*/
#include<iostream>
using namespace std;
int x;
int V[100];

int main()
{
cout<<"x=";cin>>x;
V[0]=0;
V[1]=1;
int index=2;
while (index<=x)
    {V[index]=V[index-1]+V[index-2];
      index++;
    }
cout<<"F("<<x<<")="<<V[index-1];
}

/*
La abordarile de tip PD se pot eventual practica optimizari
Acestea sunt posibile daca se observa ca in modul de compunere
a rezultatului curent cu rezultatele anterior calculate nu este nevoie
de o parcurgere a intregii structuri anterior calculate.
Concluzie :
Optimizarile intr-un PD daca sunt posibile vizeaza memorarea eficienta
doar a unui context si nu a intregului ansamblu

In cazul functiei Fibonacci observam ca compunerile vizeaza
doar ultimele doua rezultate obtinute
Putem optimiza neintretinand intreg vectorul ci doar doua
variabile auxiliare ( ultima si penultima valoare calculata )
*/