Programare dinamica

(Categoria Tehnici de programare, autor Catalin Tiseanu)

Sugestii Silviu

• poate ca nu trebuie sa spunem tot despre programare dinamica intr-un singur articol; spre exemplu putem facem doua articole: PD basic si PD advanced

Introducere

Cateva exemple "clasice"

Probleme avansate

Programare dinamica folosind bitmask

In continuare vom vedea un exemplu de programare dinamica unde vom folosi un bitmask (codificat pe un intreg) pentru a tine spatiul starilor.

Astfel sa presupunem ca avem nevoie sa tinem un vector caracteristic pentru o multime.
Daca cardinalul acesteia este suficient de mic putem folosi un intreg pentru a codifica aceasta informatie astfel:

Fie multimea A = { x₁, x₂, ... x_n }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca x_i apartine partitiei.

Desigur, aceasta reprezentare duce la o complexitate direct proportionala cu 2 ^card(A).

Exemplu

Programare dinamica folosind vectori de numere intregi

To be continued ...