回文数组

[编程题]回文数组

热度指数：6253 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

对于一个给定的正整数组成的数组 a[] ，如果将 a 倒序后数字的排列与 a 完全相同，我们称这个数组为“回文”的。

例如， [1, 2, 3, 2, 1] 的倒序是他自己，所以是一个回文的数组；而 [1, 2, 3, 1, 2] 的倒序是 [2, 1, 3, 2, 1] ，所以不是一个回文的数组。

对于任意一个正整数数组，如果我们向其中某些特定的位置插入一些正整数，那么我们总是能构造出一个回文的数组。

输入一个正整数组成的数组，要求你插入一些数字，使其变为回文的数组，且数组中所有数字的和尽可能小。输出这个插入后数组中元素的和。

例如，对于数组 [1, 2, 3, 1, 2] 我们可以插入两个 1 将其变为回文的数组 [1, 2, 1, 3, 1, 2, 1] ，这种变换方式数组的总和最小，为 11 ，所以输出为 11 。

输入描述:

输入数据由两行组成： 第一行包含一个正整数 L ，表示数组 a 的长度。 第二行包含 L 个正整数，表示数组 a 。  对于 40% 的数据： 1 < L <= 100 达成条件时需要插入的数字数量不多于 2 个。  对于 100% 的数据： 1 < L <= 1,000 0 < a[i] <= 1,000,000 达成条件时需要插入的数字数量没有限制。

输出描述:

输出一个整数，表示通过插入若干个正整数使数组 a 回文后，数组 a 的数字和的最小值。

示例1

输入

8
51 23 52 97 97 76 23 51

输出

算法知识视频讲解

JavaScript

哎呀咿呀

js版本回答

解析可以看我的博客，欢迎指正~

https://blog.csdn.net/weixin_39755630/article/details/105690385

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))

编辑于 2020-04-22 22:36:31 回复(0)