【区间dp-回文子序列-8-4】SH10 回文数组
描述
对于一个给定的正整数组成的数组 a[] ，如果将 a 倒序后数字的排列与 a 完全相同，我们称这个数组为“回文”的。
例如， [1, 2, 3, 2, 1] 的倒序是他自己，所以是一个回文的数组；而 [1, 2, 3, 1, 2] 的倒序是 [2, 1, 3, 2, 1] ，所以不是一个回文的数组。
对于任意一个正整数数组，如果我们向其中某些特定的位置插入一些正整数，那么我们总是能构造出一个回文的数组。
输入一个正整数组成的数组，要求你插入一些数字，使其变为回文的数组，且数组中所有数字的和尽可能小。输出这个插入后数组中元素的和。
例如，对于数组 [1, 2, 3, 1, 2] 我们可以插入两个 1 将其变为回文的数组 [1, 2, 1, 3, 1, 2, 1] ，这种变换方式数组的总和最小，为 11 ，所以输出为 11 。
输入描述：
输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。 对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。 对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。
输出描述：
输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。
示例1
输入：
8 51 23 52 97 97 76 23 51
输出：
598
分析题目：【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数题目要求插入后回文串的长度最短，本题要求插入后回文数组和最少。同样，也可以按照上一题解决方案二。
dp[l][r]= s[l,r]变成回文字数组之后的 最少添加的和。则可以推出dp公式：
dp[l][r]=dp[l+1][r-1] 条件 nums[l]==nums[r]
dp[l][r]=Math.min(dp[l+1][r]+nums[l],dp[l][r-1]+nums[r]); 条件 nums[l]！=nums[r]
上面可以理解成：dp[l+1][r] 其实是 变成的回文数组的左边使用了nums[l], 所以变成的回文数组的右边也要补充一个对称的nums[l], 最小和增加了一个nums[l]=dp[l+1][r]+nums[l]
初始条件dp[l][r]=0，当 l == r。
题目要求回文数组的总和最小，就是原数组和+ 最少添加的和= sum(a)+dp[0][n-1]
代码：
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNext()) { // 注意 while 处理多个 case
int n = in.nextInt();
int[] a = new int[n];
int sum = 0;
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
sum += a[i];
}
int ans = sum + minInsertions(a);
System.out.println(ans);
}
}
public static int minInsertions(int[] a) {
int n = a.length;
int[][] dp = new int[n][n];
for (int r = 0; r < a.length; r++) {
for (int l = r ; l >= 0; l--) {
if (l == r) dp[l][r] = 0;
else {
if (a[l] == a[r]) dp[l][r] = dp[l + 1][r - 1];
else dp[l][r] = Math.min(a[l] + dp[l + 1][r], dp[l][r - 1] + a[r]);
}
}
}
return dp[0][n - 1];
}
相似题目：
【区间dp-回文子序列-7】leet 516. 最长回文子序列
【区间dp-回文子序列-8-1】leet 1312. 让字符串成为回文串的最少插入次数
动态规划相关算法笔试题
