把一个数组构建成一个回文数组的最小代价

Q：把一个数组通过插入值的方式构造成一个回文数组，代价就是这个回文数组的所有元素的和，求最小代价是多少。
A：回文数组和回文字符串一般都是从两边往中间，例如开头（索引为start）的数字为4，结尾（索引为end）的数字为5。
那么一定会经历这么一步，插入一个新的4在5的后面，然后使start+1位置到end位置为回文数组，或者插入一个新的5在4的前面，使start位置到end-1位置为回文数组。
这样就得到了一个递归的过程，每次都能把大的问题变成一个更小的问题，一直到最基本的情况。

import java.util.Scanner;

public class 构造回文数组最小代价 {
    //构建memory，缓存中间结果，防止重复计算
    public static int[][] matrix;
    public static void main(String[] args) {
        Scanner in =new Scanner(System.in );
        int L =in.nextInt();
        int[] arr = new int[L];
        for(int i=0;i<L;i++){
            arr[i]=in.nextInt();
        }
        matrix=new int[arr.length][arr.length];
        int num = he(arr,0,arr.length-1);
        System.out.println(num);
    }
    public static int he(int[]a,int start,int end){
        if (matrix[start][end]!=0)
        {
            return matrix[start][end];
        }
        //两种基本情况
        if(start==end) return a[end];
        else if(start+1==end && a[start] == a[end]) return 2*a[end];
        //相等的话直接计算下一个小的问题
        else if(a[start] == a[end]) 
        {
            matrix[start+1][end-1]=he(a,start+1,end-1);
            return matrix[start+1][end-1]+ 2*a[start];
        }
        //不相等的话要做一下比较
        else{
            matrix[start+1][end]= he(a,start+1,end);
            int left = matrix[start+1][end]+ 2*a[start];
            matrix[start][end-1]= he(a,start,end-1);
            int right = matrix[start][end-1]+ 2*a[end];
            return left>right?right:left;
        }
    }
}

有了递归很容易改为DP，懒得改了。但是递归的思路真的很巧妙。如左神所说，不能要求到见到一个题就知道怎么做，要学会去试，试出递归关系，然后一步一步优化，直到DP。