Subsir comun de lungime maxima a 3 siruri

[•popoiu.george]

Din cate imi amintesc cred ca am vazut problema explicata intr-un articol chiar aici pe infoarena, dar asta era cu ceva timp in urma.

Acum cand am nevoie de rezolvarea problemei, nu am reusit sa o mai gasesc si de aceea postez aici.

Daca cunoasteti rezolvarea as fi recunoscator daca ati explica-o, sau mai bine, sa ma directionati catre articol. (daca exista)

[•Mishu91]

Cred că merge să ții o dinamică D[ i ][ j ][ k ] -> lungimea celui mai lung subșir comun luând în considerare primele i elemente din primul, primele j din al doilea, și primele k din al treilea.

D[ i ][ j ][ k ] = D[ i-1 ][ j-1 ][ k-1 ] + 1, dacă A[ i ] = B[ j ] = C[ k ].
                        max(D[ i-1 ][ j ][ k ], D[ i ][ j-1 ][ k ], D[ i ][ j ][ k-1 ]), altfel.
 

[•popoiu.george]

M-am gandit si eu la aceasta recurenta si i-am dat niste teste usoare, dar din pacate nu este corect. 

[•Mishu91]

Eu am implementat dinamica de mai sus și am dat niște teste care se pot face de mână și mi-a dat pe toate. Pune un test pe care nu ți-a dat dinamica.

[•popoiu.george]

Da, mi-a mers, cred ca gresisem la implementare, multumesc !