dp[i]表示以s[i]结尾的完全匹配的最大字符串的长度。
dp[] = ;
if( s[i] == '(' )
dp[i] = ;
开始递推 s[i] = ')' 的情况
先想到了两种情况：
1、s[i-1] = '(' 相邻匹配
这种情况下，dp [i] = dp[i-2] + 2。
2、s[i-1] = ')'
这种情况下，第一感觉是要看dp[i-1]的值，即 j...i-1是完全匹配的话，i相当于在外面再包一个括号。
如果s[i] 和 s[ i-1-dp[i-1] ] 匹配，dp[i] = dp[i-1] + 2。否则dp[i] = 0。
提交发现 WA。
不通过的数据是这个：
上图中的23列，本来23应该和2列的'('匹配，得到22。但是计算中，23列只得到了6。
加上一行代码AC了： dp[i] += dp[ i-1-dp[i-1] ];
如果当前完整块前面相邻了一个完整块，就把它的长度也算在内。
连蒙带猜的过了。。。有点水。希望以后赶紧提升。
int longestValidParentheses(char *s)
{
int n = strlen(s);
int i,cnt ,ans = ; if(n == && s == NULL) return ; dp = (int*)malloc(n*sizeof(int)); //dp[i]表示以s[i]结尾的匹配字符串的长度。 memset(dp,,n*sizeof(int)); for(i=;i<n;i++)
{
if( s[i]=='(' ){
dp[i] = ;
}
else
{ /* 0 1 2 3 4 5 6 i */
if( s[i-] == '(' ) /* ( ( ( ) ) ) ( ) */
{
int tmp = i-;
if(tmp >= )
{
dp[i] = dp[tmp] + ;
}
else
{
dp[i] = ;
}
}
/* 0 1 2 3 4 5 i ( ( ( ) ) ) ) 0 0 0 2 4 6
*/
else
{
int tmp = i--dp[i-];
if(tmp >= && s[tmp] == '(')
{
dp[i] = dp[i-] + ;
dp[i] += dp[i-dp[i]];
}
}
}
}
cnt = ;
ans = ;
for( i=n-; i>=; )
{
if(dp[i] > )
{
cnt += dp[i];
i -= dp[i]; if(cnt > ans) ans = cnt;
}
else
{
cnt = ;
--i;
}
}
free(dp); return ans;
}