回文数组 搜狐2018秋招笔试题

对于一个给定的正整数组成的数组 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 的数字和的最小值。

Example：

Input:8
      51 23 52 97 97 76 23 51
Output:598

采用动态规划

import java.util.Scanner;
/**
 * Created by Katakuly on 2018/9/2.
 */
public class Main {
    private final static int MAX = 1002;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] array = new int[length];
        int[][] dp = new int[MAX][MAX];
        for (int i = 0; i < length; i++) {
            array[i] = scanner.nextInt();
        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[i].length; j++) {
                dp[i][j] = 0;
            }
        }
        for (int i = 0; i < length; i++) {
            dp[i][i] = array[i];
        }
        for (int i = length - 2; i >= 0; --i) {
            for (int j = i + 1; j < length; ++j) {
                if (array[i] == array[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2 * array[i];
                else
                    dp[i][j] = getMin(dp[i + 1][j] + 2 * array[i], dp[i][j - 1] + 2 * array[j]);
            }
        }
        int res = dp[0][length - 1];
        System.out.println(res);
    }

    public static int getMin(int a, int b) {
        return a < b ? a : b;
    }
}