How many operations of flipping all brackets on a substring of a string of brackets are needed to make the string 'correct'?
The DP suggested in the comments by Yuval Filmus indeed works: we can solve the problem in $\mathcal{O}(n^{2})$ by DP.

First note that we may assume that intervals are not allowed to overlap. Take any two overlapping intervals $[a, b)$ and $[c, d)$. WLOG $a \leq c$. Then we can replace the two intervals with the intervals $[a, c)$ and $[\min(b, d), \max(b, d))$ that do not overlap, have shorter total length and cover exactly the same elements.

Replace opening brackets with $1$, closing brackets with $-1$. Now the problem corresponds to applying the minimum number of operations "multiply interval by $-1$" such that every prefix has nonnegative sum, and the sum over the entire array is zero.

We construct a solution left-to-right. At every position we can either start an interval, or end an active interval.

Let $DP[m][s][0]$ denote the minimum number of intervals we need to use such that every prefix sum in the first $m$ elements is nonnegative, the sum of the first $m$ elements is $s$, and we do not have an active interval. Similarly $DP[m][s][1]$ is the same value where we do have an active interval.

If the $m$th value is $1$, for $0 \leq s \leq m$ we set


$DP[m][s][0] = DP[m-1][s-1][0]$
$DP[m][s][1] = DP[m-1][s+1][1]$


Otherwise we set


$DP[m][s][0] = DP[m-1][s+1][0]$
$DP[m][s][1] = DP[m-1][s-1][1]$.


Then we end and start intervals, setting


$DP[m][s][0] = \min(DP[m][s][0], DP[m][s][1])$
$DP[m][s][1] = \min(DP[m][s][1], DP[m][s][0] + 1)$


The base case is $DP[0][0][0] = 0$, $DP[0][0][1] = 1$.

There are $\mathcal{O}(n^{2})$ states, and we do $\mathcal{O}(1)$ work to calculate each of them, therefore the algorithm runs in $\mathcal{O}(n^{2})$. The DP can be implemented to use $\mathcal{O}(n)$ memory by only storing the values of $DP$ for the current $m$.

Here is a C++ implementation of the algorithm.

#include &lt;iostream&gt;
#include &lt;vector&gt;
using namespace std;

int main() {
    string str;
    cin &gt;&gt; str;
    int n = str.size();

    vector&lt;int&gt; dp0 = {0}, dp1 = {1};
    for (int m = 1; m &lt;= n; ++m) {
        vector&lt;int&gt; nxt0(m + 1, n + 1), nxt1(m + 1, n + 1);
        for (int i = 0; i &lt; m; ++i) {
            if (str[m-1] == '(') {
                nxt0[i+1] = dp0[i];
                if (i &gt; 0) nxt1[i-1] = dp1[i];
            } else {
                nxt1[i+1] = dp1[i]);
                if (i &gt; 0) nxt0[i-1] = dp0[i];
            }
        }
        dp0 = nxt0;
        dp1 = nxt1;
        for (int i = 0; i &lt;= m; ++i) dp1[i] = min(dp1[i], dp0[i] + 1); // Start interval
        for (int i = 0; i &lt;= m; ++i) dp0[i] = min(dp0[i], dp1[i]); // Stop interval
    }
    cout &lt;&lt; dp0[0] &lt;&lt; '\n';
}