|
|
back to boardSolution the solution is dp:) dp[i][j] - contains min number of brackets of type '(', '[' for interval from i to j, that is necessary to paste in order to sequence become correct. if i'th symbol is opened bracket and jth is corresponding closing, then we can improve anser for this interval: dp[i][j] = min(dp[i][j], dp[i + 1][j - 1] + 2); if there are different brackets, then we can improve in such way: dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 2; and finally we can improve by other bracket in the middle: dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j] + 2); here, k is the position of all indices that is corresponding closing bracket for i-th; for example if(s[i] == '(') then k is the index of all k where, s[k] = ')'; here simple code: for(int i = 2; i < n; ++i) { for(int j = 0; j + i < n; ++j) { if(isOpened(s[j]) && s[j] == get(s[j + i])){ //get(c) returns corresponding closing bracket for bracket c; d[j][j + i] = d[j + 1][j + i - 1] + 2;
} else{ if(d[j + 1][j + i] < d[j][j + i - 1]) { d[j][j + i] = d[j + 1][j + i] + 2;
} else{ d[j][j + i] = d[j][j + i - 1] + 2;
} } if(isOpened(s[j])) for(int k = j; k < j + i; ++k) if(get(s[j]) == s[k]){ if(d[j + 1][k - 1] + 2 + d[k + 1][j + i] < d[j][j + i]) { d[j][j + i] = d[j + 1][k - 1] + 2 + d[k + 1][j + i];
} } } } don't forget to precount for length 1 and 2 :) good luck to everybody :) |
|
|