题意:给定T串只含小写字母的字符串,对于每串,输出回文字串的数目模10007
思路:区间合并,对于从第i个字符到第j个字符的串里面
(1)如果str[i]!=str[j],则dp[i][j]=dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1],即回文串在[i,j-1]的情况数加上[i+1,j]的情况数,再减去两种重叠部分的情况数,即属于[i+1,j-1]的情况数。
(2)如果str[i]==str[j],则dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1])+(dp[i+1][j-1]+1)=dp[i+1][j]+dp[i][j-1]+1,即回文串在[i,j-1]的情况数加上[i+1,j]的情况数,再减去两种重叠部分......
阅读全文