구간 [S, E]의 펠린드롬 판별을 위해 구간 [S+1, E-1]의 펠린드롬 판별 결과를 이용하고 있고 또한 저장하고 있으므로 동적 계획법을 적용하고 있습니다.

1. 동적 계획법을 적용하지 않았을 경우.

구간의 길이를 S라 할 때 질문 하나에 대답하기 위해 필요한 최악의 연산횟수는 S/2입니다. (양 끝부분이 계속 일치할 경우)

구간의 길이 S는 최악의 경우 N이 되므로 시간복잡도는 O(NM)이 됩니다.

2. 동적 계획법을 적용했을 경우.

최악의 경우를 고려한다면 모든 구간에 대해 질문할 것이므로 가능한 모든 구간의 조합의 개수를 고려하면 됩니다.

 예를 들어 전체 길이가 4라고 할 때 고려해야 할 구간은 [1, 1], [2, 2], [3, 3], [4, 4], [1, 2], [2, 3], [3, 4], [1, 3], [2, 4], [1, 4] 입니다.

길이를 N으로 일반화하면 N(N-1)/2가 됩니다. 모든 구간을 계산하고 나면 O(1)만에 모든 질문에 대답할 수 있게 되므로 시간복잡도는 O(N^2+M)이 됩니다.

혹시나 잘못된 점이 있다면 지적 부탁드립니다.