SPOJ - Counting The Way of Bracket Replacement (MREPLBRC)

Problem Statement:
SPOJ - MREPLBRC

Summary:
A string s contains brackets of type "(){}[]" and question marks '?'. Make it a balanced string by changing '?' to appropriate brackets, and count the number of ways to do so.

Solution:
The DP idea goes as follows:
Let W(i,j) be the number of ways to replace the question marks such that the resulting string [i..j] is balanced. Now look at s[i], the character on index i. If s[i] is a right-hand side brackets, W(i,j) is 0, since there is no way to make [i..j] balanced. Otherwise, there might be a way to balance the string.

To do so, we iterate through indexes in between i and j one by one. Call such index m. Hence we want to see whether we can break the string into two parts, [i..m] and [m+1..j], which are both balanced. For each such m, we have 2 possibilities depending on s[i]:
1. s[i] is (, {, or [. Then if s[m] corresponds to s[i] (or s[m] is '?'), we have W(i,j) += W(i+1, m-1) * W(m+1, j)
2. s[i] is '?'. Here we have several cases depending on s[m]. If s[m] is left-hand side brackets, then it is impossible for [i..m] to be balanced. If s[m] is ), }, or ], then W(i,j) += W(i+1, m-1) * W(m+1, j). Lastly if s[m] is '?', we can freely choose any pair of open-close bracket to the question marks, hence we have W(i,j) += 3 * W(i+1, m-1) * W(m+1, j).

With that, the implementation is fairly straight forward :D