백준 10942번 C++

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAX = 2001;
int pellin[MAX];
int n,m,s,e;
int cache[MAX][MAX];

int calpellin(int i, int j) {
	if (i >= j)
		return 1;

	int &answer = cache[i][j];
	
	if (answer != -1)
		return answer;

	if (pellin[i] == pellin[j])
		answer = calpellin(i + 1, j - 1);
	else
		answer = 0;
	return answer;
}

int main(void) {
	cin >> n;
	
	for (int i = 1; i <= n; i++)
		scanf("%d", &pellin[i]);
	cin >> m;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &s, &e);
		printf("%d\n", calpellin(s, e));
	}
	return 0;
}