UVA Again Palindrome(10617)

题目大意：

       给定一个字符串，问在该字符串的所有子串中，有多少个是回文？

 

解题思路：

       动态规划，设定 dp[i][j] 表示第 i 个字符到第 j 个字符里是回文的个数，设字符串为 s，则状态转移方程为：

（1）s[i] == s[j]

      dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]  + dp[i+1][j-1] + 1; 

       当s[i] == s[j]时，要考虑s[i+1]到s[j]的回文数加上s[i] 到s[j-1]的回文数，由于两者都算的s[i+1]到s[j-1]的回文数，所以要减去s[i+1]到s[j-1]的回文数，由因为s[i] == s[j]， 所以s[i] 到 s[j]也是回文，所以又要加上s[i+1] 到 s[j-1]的回文数再加上1。

（2）s[i] != s[j]

      dp[i][j] = dp[i+1][j] + dp[i][j-1] - d][i+1][j-1];  

       因为s[i] != s[j]，则只要考虑s[i+1]到s[j]的回文数加上s[i] 到s[j-1]的回文数，由于两者都算的s[i+1]到s[j-1]的回文数，所以要减去s[i+1]到s[j-1]的回文数。

 

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

long long dp[65][65];

int main()
{
	int T, m;

	cin>>T;

	while(T--)
	{		
		char s[65];
		cin>>s;
		m = strlen(s);
		memset( dp, 0, sizeof(dp) );

		for(int i = 0; i < m; i ++)
			dp[i][i] = 1;         //因为单独一个字符也是回文，所以要预先处理一下；
		for( int i = m-1; i >= 0; i-- )
		{
			for( int j = i+1; j < m; j++ )
			{
				if( s[i] == s[j] )
					dp[i][j] = dp[i][j-1] + dp[i+1][j] + 1;
				else
					dp[i][j] = dp[i][j-1] + dp[i+1][j] - dp[i+1][j-1];
			}
		}

		cout<<dp[0][m-1]<<endl;
	}

	return 0;
}