Cost mínim de parentitzar correctament (1) P76915

Donada una paraula composta només per parèntesis que obren i tanquen, cal convertir-la en una parentització correcta. L’única operació que es pot fer és girar cada parèntesi, és a dir, canviar la seva orientació. Quin és el mínim nombre de girs necessari?

Per exemple, si la paraula és “)(()((()”, llavors es pot aconseguir la parentització correcta “((())())” girant només tres parèntesis, i no es pot fer amb cost inferior.

Entrada

L’entrada consisteix en diversos casos, cadascun amb una paraula amb $n$ parèntesis que obren o tanquen. Podeu suposar que $n$ és parell i que està entre 2 i 100.

Sortida

Per a cada cas, escriviu el cost mínim de parentitzar correctament.

Pista

Encara que hi ha solucions més eficients, és suficient una programació dinàmica de cost temporal $\Theta\left(n^3 \right)$ i cost espacial $\Theta\left(n^2 \right)$.