Q：把一個數(shù)組通過插入值的方式構(gòu)造成一個回文數(shù)組，代價就是這個回文數(shù)組的所有元素的和，求最小代價是多少盯仪。
A：回文數(shù)組和回文字符串一般都是從兩邊往中間疟暖，例如開頭（索引為start）的數(shù)字為4卡儒，結(jié)尾（索引為end）的數(shù)字為5。
那么一定會經(jīng)歷這么一步俐巴，插入一個新的4在5的后面骨望，然后使start+1位置到end位置為回文數(shù)組，或者插入一個新的5在4的前面欣舵，使start位置到end-1位置為回文數(shù)組擎鸠。
這樣就得到了一個遞歸的過程，每次都能把大的問題變成一個更小的問題缘圈，一直到最基本的情況劣光。
import java.util.Scanner;
public class 構(gòu)造回文數(shù)組最小代價 {
//構(gòu)建memory，緩存中間結(jié)果糟把，防止重復(fù)計算
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绢涡，懶得改了。但是遞歸的思路真的很巧妙遣疯。如左神所說雄可，不能要求到見到一個題就知道怎么做，要學(xué)會去試，試出遞歸關(guān)系滞项，然后一步一步優(yōu)化狭归，直到DP。
