题目描述

i和j均在 其实上一个字符串的状态f(i + 1)(j - 1) 相当于从左右两边往中间靠就是上一个

i和j均不在 包含于 i在j不在 和 i不在j在 这两个情况里面

区间DP

样例

import java.util.*;

public class Main {
    static int N = 1010;
    static int n;
    static int[][] f = new int[N][N];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        n = s.length();

        //区间长度枚举
        for (int len = 1; len <= n; len++) {
            //左端点枚举
            for (int i = 0; i + len - 1 < n; i++) {
                //右端点
                int j = i + len - 1;
                //长度为1 一个字母一定是一个回文串 所以 f[i][j] = 1
                if (len == 1) {
                    f[i][j] = 1;
                } else {
                    f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                    if (s.charAt(i) == s.charAt(j)) {
                        f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                    }
                }
            }
        }
        //最后答案= 字符串长度 - 最大长度的回文串的长度
        System.out.println(n - f[0][n - 1]);
    }
}