MO417 - Questão para a prova oral

Número: 2003-078

Enunciado:
Suponha que você tenha usado duas seqüências "A" e "B" como dados de entrada para um algoritmo de programação dinâmica que resolve o problema da maior subseqüência comum entre duas seqüências. Como resultado, você obteve a seqüência "C". Neste contexto, é correto afirmar que

A) Certamente não há outra subseqüência comum a "A" e "B" com o mesmo comprimento que "C".
B) Certamente não há subseqüência comum a "A" e "B" com comprimento menor que "C".
C) Pode haver uma subseqüência comum a "A" e "B" com comprimento maior que "C", mas somente "C" é uma subseqüência de comprimento ótimo.
D) Dependendo de "A" e "B", pode haver outras seqüências com o mesmo comprimento que "C".
E) NDA

Ideia original de: José Augusto Amgarten Quitzau