처음 생각으론 s와 e가 주어졌기 때문에 인덱스를 조정해가면서 비교를 하면 되지 않을까 생각을 했다.
하지만 우리 문제의 경우 여러 질문을 하게 되고 똑같은 과정을 계속 반복을 하게 되기 때문에 시간초과가 발생하게 된다.
따라서 dp
를 통해서 계속 반복되는 부분에 대한 연산을 줄여야 한다.
우리는 반복된 연산
을 줄이는 과정에 대해서 생각을 해야한다.
일단, 위와 같이 s와 e를 입력 받았을때 우리는 아래와 같은 검증 순서를 가지게 된다.
따라서 우리는 2번의 과정에서 유리하게 쓸 dp를 하나하나 저장을 해나가면 된다
DP[s][e]의 형태는 s번째부터 e번째가 팰린드롬인지 아닌지 1 or 0으로 나타낸다고 할때, 길이 1인 녀셕들은 위와 같고 모두 1로 나타낼 수 있다.(DP[1][1] = 1 ...)
마찬가지로 길이가 2인 녀석들에 대해서도 값을 입력할 수 있다.
현재 위의 경우 서로 값이 같지 않기 때문에 모두 0으로 초기화가 될 것이다. (DP[1][2] = 0 ...)