Hello! I have WA in problem MCO16106. My code is below
from itertools import repeat
MOD = 1000000007
s = input()
n = len(s)
# dp = [[-1] * (n + 1) for i in repeat(0, (n + 1))]
def g(a, b):
cnt = 0
if (a == '(' or a == '?') and (b == ')' or b == '?'):
cnt += 1
if (a == '[' or a == '?') and (b == ']' or b == '?'):
cnt += 1
return cnt
def f(l, r):
if l > r:
return 0
if l == r:
return 1
if dp[l][r] != -1:
return dp[l][r]
ans = 0
for i in range(l + 1, r, 2):
ans = (ans + (g(s[l], s[i]) * (f(l + 1, i) * f(i + 1, r)) % MOD) % MOD) % MOD
dp[l][r] = ans
dp[l][r] %= MOD
if dp[l][r] < 0:
dp[l][r] += MOD
return ans
dp = [[-1] * (n + 1) for i in repeat(0, (n + 1))]
print(f(0, n))
I rewrote author’s c++ solution on python, but it doesn’t work. I don’t know why:( Please, help