public static String longestPalindromeDP(String s) {
    char[] str = s.toCharArray();
    int n = str.length;
    int longestBegin = 0;
    int max = 1;
    boolean table[][] = new boolean[1000][1000];
    java.util.Arrays.fill(table[0], false);
    java.util.Arrays.fill(table[1], false);
    for (int i=0; i<n; i++) {
      table[i][i] = true;
    }
    for (int i=0; i <n-1; i++) {
      if (str[i] == str[i+1]) {
        table[i][i+1] = true;
        longestBegin = i;
        max =2;
      }
    }
    for (int len = 3; len <= n; len++) {
      for (int i=0; i<n-len+1; i++) {
        int j = i+len-1;
        if (str[i] == str[j] && table[i+1][j-1]) {
          table[i][j] = true;
          longestBegin = i;
          max = len;
        }
      }
    }
    return s.substring(longestBegin,longestBegin+max);
  }