Let dp(i, j) be a boolean function that tells us if we can reduce the substring s[i][j]. Also define function l(i) and r(i), where l(i) the largest index j ≥ i such that s[i] = s[i + 1] = ... = s[j], and l(i) as the lowest left index with the mentioned property.

Now here's the code for the recurence:

dp[i][j]=0;
if (r[i]>i) dp[i][j]=dp[r[i]+1][j];
for (k=r[i]+1; k<=j; k++)
    if (s[i]==s[k])
       dp[i][j]=dp[i][j] | (dp[r[i]+1][l[k]-1]] & dp[k+1][j]);

(There are also some cornes cases)

We observe that if r(i) > i then we can transition to state dp(r(i) + 1, j) and see if we can reduce the substring s[r(i) + 1, j]. But also we can combine the substring s[i][r(i)] with some other substring s[x][y] if all their characters are equal. So we are left to reduce s[r(i) + 1][x - 1] and s[y + 1][j]. We use r(i) and l(x) because it's always better to pick these indeces instead of fixing the right point of an interval and try to extend it to the left until we get to a different character.

I know that I worded it pretty badly, but try to simulate the recurrence on the examples and it should become clear why this kind of approach works. (but take notice, I'm not 100% sure that this solution is correct)