Trecere in revista: Brute-Force, Bkt, Dynamic PRogramming, Divide et impera

teorie-tehnici-de-programare.txt

Brute-force --->> incerci toate variantele posibile 

Backtracking - te intorci daca nu mai poti inainta

Greedy - >alegi mereu cea mai buna decizie locala

- decizii pas cu pas

- nu revii asupra alegerilor


 {1,-1,3,-33,34,10,3}

 Suma maxim
 la pas elimini numarul negativ
 Greedy

 Dynamic Programming - rezolvi subprobleme si memorezi rezultatele

                  f(10) 

            f(9)         f(8)  

          f(8)  f(7)  f(7)  f(6)   

        f(7) f(6)  f(6) f(5)  

        O(1)
 
 - problema se imparte in subprobleme suprapuse

 - se memoreaza solutiile (memoizare , tabulare)

 - garanteaza optim global

 (Fibonacci)
 (problema rucsacului)
 (lis) longest increasing subsequence

 Divide et impera

 Imparti o problema in subprobleme independente

 - problema se imparte in parti mai  mici

 - rezolv subproblemele

 - apoi combin rezultatele

[1,2,3]
[7,8,9]

lista = [1,2,3,7,8,9]

O(n log n )

DEPTH FIRST

       [1,9,3,4,5,10,18,2]

       li               ls
       0                7

       [1,9,3,4]  [5,10,18,2]

     [1,9] [3,4]    [5,10] [18,2]

     [1] [9] [3][4]  [5][10] [18] [2]

   [1,9]  [3,4]      [5,10] [18,2]

  [1,3,4,9]          [2,5,10,18]

        [1,2,3,4,5,9,10,18]


        divideetimpera(li, m)
        divideetimpera(m+1, ls)
        interclasare(li, m, ls)



Recursion TREE