|
|
back to boardShow all messages Hide all messages1. 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 :) 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. actually it's correct. he is going by the increasing of the first parameter. it's like he is splitting the string, trying to get answer for a bigger string based on the smaller substrings |
|
|
