输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。 对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。 对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。
输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。
8 51 23 52 97 97 76 23 51
598
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* Dynamic Programming
*
* State:
* dp[i][j]: 表示a[i],...,a[j]中的回文子序列的最大和
*
* Initial State:
* dp[i][i] = a[i]
*
* State Transition:
* if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2 * a[i];
* else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
*
* @author wylu
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strs = br.readLine().split(" ");
int[] a = new int[n];
long sum = 0;
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(strs[i]);
sum += a[i];
}
long[][] dp = new long[n][n];
for (int i = a.length - 1; i >= 0; i--) {
dp[i][i] = a[i];
for (int j = i + 1; j < a.length; j++) {
if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2 * a[i];
else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
}
}
System.out.println(2 * sum - dp[0][n - 1]);
}
}
状态转移公式很容易想出来
规定dp[i][j]为数组nums[i:j+1]（Go数组切片表示法，不包含结束位置）的最小和。
但是还没完，还需要思考一个问题，哪里是回文数组的中心？
给定例子里面看到，好像两边都有一些同样的数字，我一开始也想着就是应该是数组中间附近是中心吧。但真的不一定是，如果给定的数组是混乱的，那么回文数组中心是不确定的。因此，我们需要以任意位置作为回文数组的中心来尝试。
也就是说，我们需要遍历所有的情况，算出所有的dp[i][j](0 <= i <= j < nums.length)。
代码如下，采用了自底向上方法实现的动态规划。
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];
for (int i = 0; i < n; i++) {
nums[i] = in.nextInt();
}
System.out.println(solve(nums));
}
public static int solve(int[] nums) {
int[][] dp = new int[nums.length][nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
dp[i][i] = nums[i];
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == nums[i]) {
dp[i][j] = dp[i + 1][j - 1] + 2 * nums[j];
} else {
int left = dp[i + 1][j] + 2 * nums[i];
int right = dp[i][j - 1] + 2 * nums[j];
dp[i][j] = left < right ? left : right;
}
}
}
return dp[0][nums.length - 1];
}
}
#include <bits/stdc++.h>
using namespace std;
int main()
{ int n; while(cin>>n){ int a[n],dp[n][n]; for(int i=0;i<n;i++){ cin>>a[i]; dp[i][i] = a[i]; } for(int j=1;j<n;j++){ for(int i=j-1;i>=0;i--){ if(a[i]==a[j]) dp[i][j] = dp[i+1][j-1]+2*a[i]; else dp[i][j] = min(dp[i+1][j]+2*a[i], dp[i][j-1]+2*a[j]); } } cout<<dp[0][n-1]<<endl; } return 0;
} 
let num=parseInt(readline())
let arr=readline().split(' ')
function find(num,arr){
let dp=[]
for(let i=num-1;i>=0;i--){
dp[i]=new Array()
dp[i][i]=parseInt(arr[i])
for(let j=i+1;j<num;j++){
if(arr[i]==arr[j]){
if(i+1>j-1){
dp[i][j]=2*parseInt(arr[i])
}else{
dp[i][j]=dp[i+1][j-1]+2*parseInt(arr[i])
}
}else{
dp[i][j]=Math.min(dp[i+1][j]+2*parseInt(arr[i]),dp[i][j-1]+2*parseInt(arr[j]))
}
}
}
return dp[0][num-1]
}
console.log(find(num,arr)) 
#include<iostream>
#include<algorithm>
using namespace std;
/**
* 状态定义：
* dp[i][j]表示从i到j的子串构成回文子串需要插入的数字和的最小值
* 递推式：
* dp[i][j]=dp[i+1][j-1], if a[i]=a[j]
* dp[i][j]=min(dp[i+1][j]+a[i],dp[i][j-1]+a[j]), if a[i]!=a[j]
* 边界条件：
* dp[i][i]=0
* 如此，题目要求的数组和就等于：
* dp[0][L-1]+accumulate(a,a+L,0)
*/
int solve(int a[], int L){
int dp[L][L];
for(int i=L-1;i>=0;i--){
dp[i][i]=0;
for(int j=i+1;j<L;j++){
if(a[i]==a[j]) dp[i][j]=dp[i+1][j-1];
else
dp[i][j]=min(dp[i+1][j]+a[i], dp[i][j-1]+a[j]);
}
}
return dp[0][L-1];
}
int main(){
int L;
cin>>L;
int a[L];
for(int i=0;i<L;i++)
cin>>a[i];
cout<<solve(a, L)+accumulate(a,a+L,0)<<"\n";
return 0;
} 最近在学DP，没想到这个递推式不到10min就想出来了，hhhhhimport sys n = int(input()) lines = sys.stdin.readline().strip().split() values = list(map(int, lines)) dp = [[0]*n for _ in range(n)] s = 0 for i in range(n-1, -1, -1): dp[i][i] = values[i] s += values[i] if i == n-1: continue for j in range(i+1, n): if values[i] == values[j]: dp[i][j] = dp[i+1][j-1] + values[i] * 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) # print(s*2 - dp[0][n-1])
import sys n = int(input()) line1 = sys.stdin.readline().strip() values = list(map(int,line1.split())) l,r=0,n-1 while l<r: if values[l]==values[r]: l+=1 r-=1 elif values[l]<values[r]: values.insert(r+1,values[l]) l+=1 elif values[l]>values[r]: values.insert(l,values[r]) l+=1 r-=1 print(sum(values))求解，上面代码有什么问题，牛客通过率很低，本地IDE测试可以通过
import java.util.Scanner;
public class Main {
public static void main( String[] args ) {
Scanner sc = new Scanner( System.in );
while ( sc.hasNext() ) {
int n = sc.nextInt();
int[][] dp = new int[n][n];
for( int i = 0; i < n; i ++ ) dp[i][i] = sc.nextInt();
for( int len = 2; len <= n; len ++ ) {
for( int i = 0; i + len <= n; i ++ ) {
int a = i, b = i+len-1;
if( dp[a][a] == dp[b][b] )
dp[a][b] = 2*dp[a][a] + dp[a+1][b-1];
else dp[a][b] = Math.min(
2*dp[a][a] + dp[a+1][b],
2*dp[b][b] + dp[a][b-1] );
}
}
System.out.println( dp[0][n-1] );
}
}
}
import java.util.Scanner;
public class PalindromeArray {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int len = sc.nextInt();
int[] nums = new int[len];
for (int i = 0; i < len; i++) {
nums[i] = sc.nextInt();
}
Integer[][] dp = new Integer[len][len];
int res = palindromeArrayHelper(nums, dp, 0, len - 1);
System.out.println(res);
}
sc.close();
}
public static int palindromeArrayHelper(int[] nums, Integer[][] dp, int i, int j) {
if (i > j) {
return 0;
}
if (i == j) {
return nums[i];
}
if (dp[i][j] != null) {
return dp[i][j];
}
if (nums[i] == nums[j]) {
dp[i][j] = 2 * nums[i] + palindromeArrayHelper(nums, dp, i + 1, j - 1);
} else {
dp[i][j] = Math.min(2 * nums[i] + palindromeArrayHelper(nums, dp, i + 1, j),
2 * nums[j] + palindromeArrayHelper(nums, dp, i, j - 1));
}
return dp[i][j];
}
}
#include <iostream>
#include <algorithm>
using namespace std;
int FindMinSum(int input[], int left, int right);
int matrix[1000][1000];
int main(){
int size;
cin >> size;
int* input = new int[size];
for (int i = 0; i < size; i++)
cin >> input[i];
int sum = FindMinSum(input, 0, size - 1);
cout << sum;
system("pause");
return 0;
}
int FindMinSum(int input[], int left, int right){
if (left == right)
return input[left];
if (left > right)
return 0;
if (input[left] == input[right]){
if (matrix[left + 1][right - 1] == 0)
matrix[left + 1][right - 1] = FindMinSum(input, left + 1, right - 1);
return 2 * input[left] + matrix[left + 1][right - 1];
}
else{
if (matrix[left][right - 1] == 0)
matrix[left][right - 1] = FindMinSum(input, left, right - 1);
if (matrix[left + 1][right] == 0)
matrix[left + 1][right] = FindMinSum(input, left + 1, right);
return min(matrix[left][right - 1] + 2 * input[right], matrix[left + 1][right] + 2 * input[left]);
}
} 
#include<iostream>
(720)#include<vector>
#include<algorithm>
using namespace std;
class Game {
public:
vector<int> data;
int huiwen(int begin, int end, vector<int>& data, vector<vector<int>>& memo);
int huiwen(void);
};
int Game::huiwen(void)
{
int n = data.size();
vector<int> col(n, -1);
vector<vector<int>> memo(n, col);
return huiwen(0, n - 1, data, memo);
}
int Game::huiwen(int begin, int end, vector<int>& data, vector<vector<int>>& memo)
{
if (begin == end)
{
memo[begin][end] = data[begin];
return data[begin];
}
if (data[begin] == data[end])
if (begin + 1 == end)
memo[begin][end] = 2 * data[begin];
else
{
if (memo[begin + 1][end - 1] != -1)
memo[begin][end] = memo[begin + 1][end - 1] + 2 * data[begin];
else
memo[begin][end] = huiwen(begin + 1, end - 1, data, memo) + 2 * data[begin];
}
else
{
if (memo[begin + 1][end] != -1 && memo[begin][end - 1] != -1)
memo[begin][end] = min(memo[begin + 1][end] + 2 * data[begin], memo[begin][end - 1] + 2 * data[end]);
else
memo[begin][end] = min(huiwen(begin + 1, end, data, memo) + 2 * data[begin], huiwen(begin, end - 1, data, memo)+ 2 * data[end]);
}
return memo[begin][end];
}
int main(void)
{
Game game;
int n = 0;
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
game.data.push_back(temp);
}
int res = game.huiwen();
cout << res << endl;
return 0;
} 
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
int num[N];
for (int i = 0; i < N; i++) {
cin >> num[i];
}
// sums 存储了从j到i的最小和，每次新增第i个数字，则
// 需要更新每一个可能区间的结果，以便添加下一个数字时，
// 能够知道上一个数字添加后每个可能区间的最小值。
// 3 2 1 5 3
// i = 1
// j = 0
// [0,1]区间最小值：3 != 2 => 2 3 2 => 7
// i = 2
// j = 1
// [1,2]区间最小值：2 != 1 => min(sums[1, 1] + 2 * num[2], sums[2, 2] + 2*nums[1])
// [0,2]区间最小值：3 != 1 => min(sums[1, 2] + 2 * num[0], sums[0, 1] + 2 * nums[2])
// ...
// i = 4
// j = 3
// [3, 4]区间最小值：...
// ...
// [0, 4]区间最小值：3 == 3 => sums[1, 3] + 2 * num[i]
int sums[N][N] = {0};
for (int i = 1; i < N; i++) {
sums[i][i] = num[i];
for (int j = i - 1; j >= 0; j--) {
if (num[i] == num[j]) {
sums[i][j] = sums[i - 1][j+1] + 2 * num[i];
} else {
sums[i][j] = min(sums[i-1][j] + 2 * num[i], sums[i][j + 1] + 2 * num[j]);
}
}
}
return sums[N-1][0];
} 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long []arr=new long[n];
for(int i=0;i<arr.length;i++){
arr[i]=sc.nextLong();
}
long [][]dp=new long[n+1][n+1];
long sum=0;
for(int i=0;i<n;i++){
dp[0][i]=0;
sum+=arr[i];
}
for(int i=0;i<n;i++){
dp[i][0]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i-1]==arr[n-j]){
dp[i][j]=dp[i-1][j-1]+arr[i-1];
}else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
System.out.println((sum-dp[n][n])*2+dp[n][n]);
}
}
//就是left right对比，如果相同，往中间移动，如果不相同，则添加一个元素，并移动
//值得注意的是，因为不相同的时候，递归会重复计算很多次，所以可以采用记录的方法，加快速度
#include "iostream"
#include "vector"
using namespace std;
int sumValue(vector<vector<int>>& tempResult,vector<int>& myVec, int left, int right)
{
if(left==right)
return myVec[left];
if(left>right)
return 0;
if(myVec[left]==myVec[right])
{
if(tempResult[left+1][right-1]==0)
tempResult[left+1][right-1]= sumValue(tempResult,myVec,left+1,right-1);
return tempResult[left+1][right-1] + 2*myVec[left];
}
else
{
if(tempResult[left][right-1]==0)
tempResult[left][right-1]= sumValue(tempResult,myVec,left,right-1);
int leftValue = tempResult[left][right-1] + 2*myVec[right];
if(tempResult[left+1][right]==0)
tempResult[left+1][right]= sumValue(tempResult,myVec,left+1,right);
int rightValue = tempResult[left+1][right] + 2*myVec[left];
return leftValue<rightValue?leftValue:rightValue;
}
}
int main()
{
int L=0;
cin>>L;
vector<int> myVec(L);
vector<vector<int>> tempResult(L);
for(int i=0;i<tempResult.size();i++)
tempResult[i].resize(L);
for(int i=0;i<L;i++)
{
int temp = 0;
cin>>temp;
myVec[i] = temp;
}
int sumVal = sumValue(tempResult,myVec,0,myVec.size()-1);
cout<<sumVal;
return 0;
} 
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
