백준 5502 팰린드롬

문제
팰린드롬이란 대칭 문자열이다. 즉, 왼쪽에서 오른쪽으로 읽었을때와 오른쪽에서 왼쪽으로 읽었을때 같다는 얘기다. 당신은 문자열이 주어졌을때, 최소 개수의 문자를 삽입하여 팰린드롬이 되게 되는 문자의 개수를 구하는 프로그램을 작성하여라.

예제에서는, 2개의 문자를 삽입하여 팰린드롬이 된다. "Ab3bd"는 "dAb3bAd" 혹은 "Adb3bdA" 로 바뀔 수 있다. 하지만, 2개 미만의 문자를 삽입해서는 팰린드롬이 될 수 없다.

골이 아픈 문제였다 최고로 긴 팰린드롬을 찾아서 그 길이 만큼 전체 길이에서
빼주면 된다고 생각했는데 최장 팰린드롬을 어떻게 찾아야할지 막막했다.

최장 팰린드롬은 ex )  (a) bc (a)
문자열 S와 reverse(S) 한 것의 LIS를 구하면 
최고로 긴 비 연속 팰린드롬을 찾을 수 있는 것이였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String s = br.readLine();
        String srv = new StringBuilder(s).reverse().toString();
        if(s.equals(srv)) {
            System.out.println(0);
            return;
        }

        int DP[][] = new int[N+1][N+1];
        for(int i = 1; i <= N; i++) {
             for(int j = 1; j <= N; j++) {
                 if(s.charAt(j - 1) == srv.charAt(i - 1)) {
                     DP[i][j] = DP[i - 1][j - 1] + 1;
                 } else {
                     DP[i][j] = Math.max(DP[i - 1][j], DP[i][j - 1]);
                 }
             }
        }




        System.out.println(N - DP[N][N]);
    }


}