對(duì)于一個(gè)給定的正整數(shù)組成的數(shù)組 a[] ，如果將 a 倒序后數(shù)字的排列與 a 完全相同，我們稱這個(gè)數(shù)組為“回文”的。例如， [1, 2, 3, 2, 1] 的倒序是他自己，所以是一個(gè)回文的數(shù)組；而 [1, 2, 3, 1, 2] 的倒序是 [2, 1, 3, 2, 1] ，所以不是一個(gè)回文的數(shù)組。
對(duì)于任意一個(gè)正整數(shù)數(shù)組，如果我們向其中某些特定的位置插入一些正整數(shù)，那么我們總是能構(gòu)造出一個(gè)回文的數(shù)組。輸入一個(gè)正整數(shù)組成的數(shù)組，要求你插入一些數(shù)字，使其變?yōu)榛匚牡臄?shù)組，且數(shù)組中所有數(shù)字的和盡可能小。輸出這個(gè)插入后數(shù)組中元素的和。例如，對(duì)于數(shù)組 [1, 2, 3, 1, 2] 我們可以插入兩個(gè) 1 將其變?yōu)榛匚牡臄?shù)組 [1, 2, 1, 3, 1, 2, 1] ，這種變換方式數(shù)組的總和最小，為 11 ，所以輸出為 11 。
輸入描述：

輸入數(shù)據(jù)由兩行組成： 第一行包含一個(gè)正整數(shù) L，表示數(shù)組 a 的長(zhǎng)度。第二行包含L個(gè)正整數(shù)，表示數(shù)組 a。  
對(duì)于 40% 的數(shù)據(jù)：1<L<=100 達(dá)成條件時(shí)需要插入的數(shù)字?jǐn)?shù)量不多于2個(gè)。
 對(duì)于 100% 的數(shù)據(jù)：1 < L<=1,000 0<a[i]<=1,000,000 達(dá)成條件時(shí)需要插入的數(shù)字?jǐn)?shù)量沒(méi)有限制。

輸出描述：

輸出一個(gè)整數(shù)，表示通過(guò)插入若干個(gè)正整數(shù)使數(shù)組 a 回文后，數(shù)組 a 的數(shù)字和的最小值。

Example：

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

采用動(dòng)態(tài)規(guī)劃

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;
    }
}