【题意说明】
括号匹配问题。
定义一个合法的括号序列:
(1)空串是合法的序列;
(2)如果s是个合法的序列,则(s)和[s]也都是合法的序列;
(3)如果a和b都是合法的序列,则ab也是合法的序列;
(4)再没有其它情况能组成合法的序列。
现在给你一个由(、)、[和]构成的序列,求其合法子串最长的长度。其子串的要求是:
若原串为a1a2a3……an,其子串为ai1ai2……aik,要求1<=i1<i2<……<ik<=n。
【问题分析】
用f[i][j]表示第i位置起,长度为j的合法子串最长长度,则有:
f[i][j]=max{max(f[i][k]+f[i+k][j-k]), g(i,i+j-1)+f[i+1][j-2]} {0<k<j}。
其中:g(x,y)表示位置x与位置y是否匹配,若匹配则返回1,否则返回0。
其中f[0]=f[1]={0};
f[0][n]即为所求的结果。