作者windows2k (代替孟子来惩罚你)
看板ACMCLUB
标题Re: [问题] 10157
时间Sun Jul 31 22:58:25 2005
※ 引述《DJWS (...)》之铭言：
: 这样问或许很突兀
: 但我很想知道针对每个query 时间复杂度为O(n*d)的解法
: 可以教我吗? :p
现在限制深度为 d
f[i][j]代表长度为i,左括弧比右括弧多j个的情形,且最多不会多出 d 个
f[i][j]=f[i-1][j+1] (最右边是 ')') + f[i-1][j-1] (最右边是 '(' )
边界条件
f[0][0]=1
f[i][j]=0 if j > d
求解目标:
f[n][0]
--
希望没写错啦...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.220.139