Salut la toata lumea.
Am gasit intr-o culegere o problema ce suna cam asa:
Se dau N cuvinte (cuvintele contin doar caracterele 'a' ... 'z') si se cere sa se gaseasca cea mai lunga secventa astfel incat pentru fiecare cuvant i din secventa, prima litera a cuvantului i sa fie mai mare decat ultima litera a cuvantului i-1.
De exemplu : N = 4 si cuvintele sunt ana, capat, merge, repede.
Raspuns: cea mai lunga secventa = 3, secventa ana merge repede.
Cuvintele se pot gasi si in alta ordine decat cea initiala.
Solutii ca backtracking sau reprezentarea celor N cuvinte sub forma unui graf orientat si gasirea celui mai lung lant elemntar am gasit si eu. As vrea daca stie cineva daca aceasta problema se poate rezolva cu programare dinamica si daca da cum se poate, sa-mi dea un hint, sau sa-mi explice algoritmul (problema nu e departe de problema
Zmeu2 de la OJI 2003) .
V-as fi recunoscator daca mi-ati oferi un raspuns. Va multumesc frumos si o zi buna!