Algoritmia - Ayuda en un ejercicio: Hallar la cantidad de cadenas balanceadas de tamaño 2n con profundidad d

 
Vista:

Ayuda en un ejercicio: Hallar la cantidad de cadenas balanceadas de tamaño 2n con profundidad d

Publicado por Arturo (4 intervenciones) el 12/01/2014 19:27:05
Ayuda para resolver el siguiente problema:
-> Hallar la cantidad de cadenas balanceadas de tamaño 2n con profundidad d. Después devolverlas todas eficientemente.
La profundidad de una cadena se define como: la máxima cantidad de paréntesis abiertos sin balancear que se encuentra en alguno de los prefijos.
Tenemos un algoritmo (diseñado con programación dinámica) que es O(n**3). Sería bueno si pudieran dar uno mejor o sino dar una cota mínima.
Para devolverlas no tenemos un algoritmo bueno.
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder