Bien, entonces le pregunté a Kunal Kukreja, Él me ayudó con la recurrencia.
Entonces el estado dp toma 2 parámetros, (índice, valor)
dp (índice, valor) se define como el no. de subsecuencias que terminan en el índice que tienen un valor de valor.
- ¿Cómo podemos implementar el algoritmo de Prim rápidamente en los concursos de programación?
- ¿Cuál es el algoritmo correcto para realizar la diferenciación usando un programa de computadora para cualquier función ingresada por el usuario?
- ¿Un montón necesita usar una cola prioritaria?
- ¿Cómo explica la localidad de caché el hecho de que la ordenación rápida suele ser más rápida que la ordenación por fusión?
- ¿Cuál es el mejor título de proyecto para la estructura de datos del sujeto y el algoritmo?
El valor, por otro lado, se define como el número de ‘(‘ s – el número de ‘)’ s.
Entonces, la recurrencia básica que obtenemos es:
dp [index] [value] = If str [index] == ‘(‘ Suma de (dp [k] [value-1]) para k <index
dp [index] [value] = If str [index] == ‘)’ Suma de (dp [k] [value + 1]) para k <index
El caso base se devuelve cuando el valor == 1, agregamos 1 al valor de retorno si el carácter actual es ‘(‘.
if (valor == 1 && str [índice] == ‘(‘) dp [índice] [valor] ++
Como el número de ‘)’ no puede exceder el número de ‘)’ en una subsecuencia, no permitimos -ve valores de Value como estado legítimo.
Tiempo de ejecución: O (n ^ 3) // Dado que el valor en max será n, donde n es el tamaño de la cadena
Memoria: O (n ^ 2)
Aquí hay un enlace a una implementación de arriba hacia abajo http://ideone.com/j5bGCV
