第一次做dp求最长回文的题目 记录一下
看题解会的 这思路很巧妙 有被打击到 日常被题虐

要求把长度为$n$的串 加上$k$个字符 补全为回文串 求$k_{min}$

加上至少$k$个字符 恰好能补成一个回文串 也就是说 没加之前 原字符串刚好有$k$个字符落单
而剩下的$n-k$个字符组成一个现成的回文串 也就不需要改变

而我们要求的是$k$ 直接求解比较困难 因此换个方向 求一下当前字符串中现成的最长的那个回文串
字符串全长-最长回文串的长度=落单的字符个数 也就是$k$

区间DP 求最长回文序列

$f(i,j)$ “只考虑区间$[i,j]$的字符，能组成的回文串集合”
属性 $len_{max}$

状态计算

• $a_i$，$a_j$都不选：$f(i,j) = f(i + 1, j - 1)$
• 选$a_i$不选$a_j$：$f(i,j) = f(i, j - 1)$
• 不选$a_i$选$a_j$：$f(i,j) = f(i + 1, j)$
• $a_i$，$a_j$都选（此时必须满足$a_i==a_j$ 两个都选即总长度+2）：$f(i,j) = f(i + 1, j - 1) + 2$
• 第一种情况其实已经被包含于第二第三里了 类似于“求最长公共子序列” 所以最终的状态计算式为$f(i,j)=max(f(i+1,j), f(i,j-1), f(i+1,j-1)+2)$

注意
如果$i==j$时，同样满足$a_i==a_j$ 但此时两者其实表示同一个位置上的字符 +2是错误的
所以需要对这一情况进行特判 即$i==j$时$f(i,j)=1$

区间DP 一般先枚举长度再枚举起点 从而计算中点 有的题目还要接着枚举分界点 但本题只需要判断起点终点字符即可

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = 1010;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        char[] words = (" " + scanner.next()).toCharArray();  // 加个占位
        int n = words.length - 1;
        for (int len = 1; len <= n; len++) {  // 枚举长度
            for (int i = 1; i + len - 1 <= n; i++) {  // 枚举起点
                int j = i + len - 1;  // 计算终点
                if (i == j) f[i][j] = 1;  // 对于i==j 特判
                else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    if (words[i] == words[j])
                        f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                }
            }
        }
        System.out.println(n - f[1][n]);
    }
}

当然 也可以直接枚举起点和终点 但注意区间长度要从小到大
因为状态计算用到$i+1$ 所以$i$要从大到小枚举 确保当前使用的$i+1$是已经更新过了的
同理 用到了$j-1$ 所以$j$要从小到大枚举

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = 1010;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        char[] words = (" " + scanner.next() + " ").toCharArray();
        n = words.length - 2;
        for (int i = n; i > 0; i--) {
            for (int j = i; j <= n; j++) {
                f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                if (i == j) f[i][j] = 1;
                else if (words[i] == words[j]) 
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
            }
        }
        System.out.println(n - f[1][n]);
    }
}