SRM 607 L2 D2：PalindromicSubstringsDiv2，DP

题目：http://community.topcoder.com/stat?c=problem_statement&pm=12967

暴力法会超时，dp[i][j] 表示 子串 [i...j] 是否为回文串。

代码：

#include <algorithm>
#include <iostream>
#include <sstream>

#include <string>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <cstring>

#include<ctime>

using namespace std;


#define CHECKTIME() printf("%.2lf\n", (double)clock() / CLOCKS_PER_SEC)


/*************** Program Begin **********************/

bool dp[5000][5001];

class PalindromicSubstringsDiv2 {
public:
    int count(vector <string> S1, vector <string> S2) {
        memset(dp, 0, sizeof(dp));
	int res = 0;
	string S;
	for (int i = 0; i < S1.size(); i++) {
		S += S1[i];
	}
	for (int i = 0; i < S2.size(); i++) {
		S += S2[i];
	}
	int N = S.size();

	for (int i = 0; i < N; i++) {
		dp[i][i] = true;
		++res;
	}
	for (int len = 2; len <= N; len++) {
		for (int i = 0; i <= N - len; i++) {
			if (S[i] == S[i + len - 1]) {
				if (len == 2 || dp[i+1][i + len - 2] == true) {
					dp[i][i+ len - 1] = true;
					++res;
				}

			}
		}
	}

        return res;
    }
};

/************** Program End ************************/

SRM 607 L2 D2：PalindromicSubstringsDiv2，DP

原文：http://blog.csdn.net/xzz_hust/article/details/18988671