dp[i][j]表示i到j区间至少要加多少数才能形成回文串
分两种情况分析
dp[i][j] = dp[i + 1][j - 1];两端相等
dp[i][j] = Math.min(dp[i + 1][j],dp[i][j - 1]) + 1;两端不等

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] A = br.readLine().toCharArray();
        int len = A.length;
        int[][] dp = new int[len][len];
        for (int i = len - 2; i >= 0; i--) { //因为要算dp[i][i + 2]需要先知道dp[i][i + 1]与dp[i + 1][i + 2]的值，所以i倒着遍历
            for (int j = i + 1; j < len; j++) {
                if(A[i] == A[j]) {
                    dp[i][j] = dp[i + 1][j - 1]; //如果i + 1 == j,则dp[j][i] = 0,符合答案
                } else {
                    dp[i][j] = Math.min(dp[i + 1][j],dp[i][j - 1]) + 1;
                }
            }
        }
        System.out.println(dp[0][len - 1]);
    }

}