some hints

Posted by

hliu20 18 May 2013 15:26

1. DP, f[i][j] represents when solving the substring from index i to j the minimum brackets should add. Then we have

1) i <= j

2) if i == j, then f[i][j] = 1. (you can add a bracket to match the one)

3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j]) i<=k<=(j-1)

4) that's not the end.... a case when s[i] == s[j], get f[i+1][j-1]. should compare this value to above values in (3), and get the maximum.

2. how to show the results

when calculate f[i][j], you can use an array like ans[i][j] to record the way to get f[i][j]. for example, when f[i][j] get maximum when k = k1. so you can record k1 to ans[i][j]. Or f[i+1][j-1] get the maximum , you can record -1 to ans[i][j], or in the case i==j you get the maximum, set ans[i][j] to 0......

Then you can get result by DFS.

hope it helps :)

Re: some hints

Posted by

Dmitriy 12 Feb 2018 14:20

3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j]) i<=k<=(j-1)

> f[i][j] = min(f[i][k], f[k+1][j]

You determine f(k) on f(k + 1) in main cycle. But f(k + 1) is undefine for a while.

It's a good hint, but something is wrong.