Nc1033 palindrome substring of small a (ring, interval DP)

Original link

Because it is a palindrome substring problem , First of all, we should think about how to deal with the palindrome string problem

• Substring ： Successive
• Subsequence ： Discontinuous

For substring, the method similar to subsequence can be adopted

  Boundary treatment is different

initialization ： All for false

The border ：len==1 Set to true  len==2 And s[i]==s[j],dp[i][j]=true

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
bool dp[2*N][2*N];
int main()
{
	string s;
	cin >> s;

	int n = s.size();
	s = s + s;
	int res = 0;
	for (int len = 1;len <= n;len++)
		for (int i = 0;i + len - 1 < 2 * n;i++)
		{
			int j = i + len - 1;
			if (len == 1)
				dp[i][j] = true;
			else if (len == 2 && s[i] == s[j])
				dp[i][j] = true;
			else
			{
				
				if (s[i] == s[j])
					dp[i][j]|=dp[i+1][j-1];
			}
			if (dp[i][j])
					res = max(res, len);
		}
	cout << res;
}