ac

给定一个字符串str，如果可以在str的任意位置添加字符，请返回在添加字符最少的情况下，让str整体都是回文字符串的一种结果。

dp[i][j] 表示 str[i...j] 的结果

str[i] == str[j]  问题变成 dp[i+1...j-1]

否则，先处理 str[i+1...j] 补个 str[i]，或者 处理 str[i...j-1] 补个 str[j]

abdbe

i,j相差为1的
dp[0][1] dp[1][2] dp[2][3] dp[3][4]

那么就可以求i,j相差为2的了
dp[2][4] = Min(dp[3][4], dp[2][3]) + 1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


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

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        String nStr = reader.readLine();
        int n = nStr.length();
        char[] chars = nStr.toCharArray();
        int[][] dp = new int[n][n];
        for(int i=1;i<n;i++){
            // 从距离为1的一直处理到距离为n
            for(int j=0;j<n;j++){
                int k1 = j;
                int k2 = k1 + i;
                if(k2 >= n){
                    continue;
                }
                // 距离是1
                if(i == 1){
                    if(chars[k1] == chars[k2]){
                        dp[k1][k2] = 0;
                    }else {
                        dp[k1][k2] = 1;
                    }
                }else { // 距离是其它
                    if(chars[k1] == chars[k2]){
                        dp[k1][k2] = dp[k1+1][k2-1];
                    }else {
                        dp[k1][k2] = Math.min(dp[k1+1][k2], dp[k1][k2-1]) + 1;
                    }
                }
            }
        }
        int need = dp[0][n-1];

        // 构造一种方案
        char[] ans = new char[n+need];
        int ansI = 0;
        int ansJ = n + need - 1;
        int sta = 0;
        int end = n - 1;
        while (sta <= end){
            if(chars[sta] == chars[end]){
                ans[ansI++] = chars[sta];
                ans[ansJ--] = chars[sta];
                sta++;
                end--;
            }else {
                if(dp[sta+1][end] < dp[sta][end-1]){
                    // 左侧加字符
                    ans[ansI++] = chars[sta];
                    ans[ansJ--] = chars[sta];
                    sta ++;
                }else if(dp[sta+1][end] > dp[sta][end-1]){
                    // 右侧加字符
                    ans[ansI++] = chars[end];
                    ans[ansJ--] = chars[end];
                    end --;
                }else {
                    // 随便选择一个
                    ans[ansI++] = chars[sta];
                    ans[ansJ--] = chars[sta];
                    sta ++;
                }
            }
        }
        System.out.println(ans);
    }
}
/*
ABA

ABA

AB
ABA
*/