E' un esercizio che si presta ad un'applicazione della programmazione dinamica.
Per che ha praticato la programmazione dinamica, una tale soluzione dovrebbe fluire abbastanza pedissequa, senza riservare particolari sorprese ne' dolori.
Eccetto il fatto che la programmazione dinamica, che e' quadratica, non si presterebbe a risolvere le istanze piu' grandi.
E' possibile qui concepire dei semplici algoritmi lineari di tipo greedy che sfruttano la particolare struttura di questo problema.

Ad esempio: finche' conteniamo la sottostringa "()" la possiamo rimuovere a costo 0.
La stringa rimanente avra' la forma:  ))))))))))))((((
ossia h chiuse seguite da k aperte.
E su questo caso altamente strutturato possiamo dare la soluzione in forma chiusa.
Riesci a vederla?

La soluzione da me proposta e' ancora piu' rapida basandosi su una semplice scansione da sinistra a destra con aggiornamenti di un paio di variabili di conteggio.