搜狐编程回文数组Java

import java.util.*;

public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);

int n = in.nextInt();
int[] nums = new int[n];
int sum = 0;
for(int i = 0; i < n; i++){
nums[i] = in.nextInt();
sum += nums[i];
}
System.out.println(sum + new Main().helper(n, nums));
in.close();
}
public int helper(int n, int[] nums) {
int[][] dp = new int[n][n];
for(int i = n-2; i >= 0; i--){
for(int j = i + 1; j < n; j++){
if(nums[i]== nums[j]){
dp[i][j] = dp[i+1][j-1];
} else {
dp[i][j] = Math.min(dp[i+1][j] + nums[i] , dp[i][j-1] + nums[j]);
}
}
}

return dp[0][n-1];
}
}
#搜狐##Java工程师#