给定一个正整数数组。我们需要将给定的数组设置为“回文”。唯一允许的操作是“合并”（两个相邻元素）。合并两个相邻的元素意味着用它们的和替换它们。任务是找到使给定数组成为“回文”所需的最小合并操作数。 要使任何数组成为回文，我们只需应用合并操作n-1倍，其中n是数组的大小（因为单个元素数组总是回文的，类似于单个字符串）。在这种情况下，数组的大小将减少到1。但在这个问题上，我们被要求以最少的操作次数来完成。
null
例子：
Input : arr[] = {15, 4, 15}Output : 0Array is already a palindrome. So wedo not need any merge operation.Input : arr[] = {1, 4, 5, 1}Output : 1We can make given array palindrome withminimum one merging (merging 4 and 5 tomake 9)Input : arr[] = {11, 14, 15, 99}Output : 3We need to merge all elements to makea palindrome.
预期的时间复杂度为O（n）。
设f（i，j）为使子阵arr[i..j]成为回文的最小合并操作。如果i==j，答案是0。我们从0开始i，从n-1开始j。
- 如果arr[i]==arr[j]，则不需要在索引i或索引j处进行任何合并操作。在这种情况下，我们的答案将是f（i+1，j-1）。
- 否则，我们需要进行合并操作。出现以下情况。
- 如果arr[i]>arr[j]，那么我们应该在索引j处进行合并操作。我们合并索引j-1和j，并更新arr[j-1]=arr[j-1]+arr[j]。在这种情况下，我们的答案是1+f（i，j-1）。
- 对于arr[i]
- 我们的答案是f（0，n-1），其中n是数组arr[]的大小。
因此，可以使用两个指针（第一个指针指向数组的开头，第二个指针指向数组的最后一个元素）方法迭代地解决这个问题，并保持到目前为止完成的合并操作总数的计数。 下面是上述想法的实现。
C++
// C++ program to find number of operations // to make an array palindrome #include <bits/stdc++.h> using namespace std; // Returns minimum number of count operations // required to make arr[] palindrome int findMinOps( int arr[], int n) { int ans = 0; // Initialize result // Start from two corners for ( int i=0,j=n-1; i<=j;) { // If corner elements are same, // problem reduces arr[i+1..j-1] if (arr[i] == arr[j]) { i++; j--; } // If left element is greater, then // we merge right two elements else if (arr[i] > arr[j]) { // need to merge from tail. j--; arr[j] += arr[j+1] ; ans++; } // Else we merge left two elements else { i++; arr[i] += arr[i-1]; ans++; } } return ans; } // Driver program to test above int main() { int arr[] = {1, 4, 5, 9, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Count of minimum operations is " << findMinOps(arr, n) << endl; return 0; } |
JAVA
// Java program to find number of operations // to make an array palindrome class GFG { // Returns minimum number of count operations // required to make arr[] palindrome static int findMinOps( int [] arr, int n) { int ans = 0 ; // Initialize result // Start from two corners for ( int i= 0 ,j=n- 1 ; i<=j;) { // If corner elements are same, // problem reduces arr[i+1..j-1] if (arr[i] == arr[j]) { i++; j--; } // If left element is greater, then // we merge right two elements else if (arr[i] > arr[j]) { // need to merge from tail. j--; arr[j] += arr[j+ 1 ] ; ans++; } // Else we merge left two elements else { i++; arr[i] += arr[i- 1 ]; ans++; } } return ans; } // Driver method to test the above function public static void main(String[] args) { int arr[] = new int []{ 1 , 4 , 5 , 9 , 1 } ; System.out.println( "Count of minimum operations is " + findMinOps(arr, arr.length)); } } |
Python3
# Python program to find number of operations # to make an array palindrome # Returns minimum number of count operations # required to make arr[] palindrome def findMinOps(arr, n): ans = 0 # Initialize result # Start from two corners i,j = 0 ,n - 1 while i< = j: # If corner elements are same, # problem reduces arr[i+1..j-1] if arr[i] = = arr[j]: i + = 1 j - = 1 # If left element is greater, then # we merge right two elements elif arr[i] > arr[j]: # need to merge from tail. j - = 1 arr[j] + = arr[j + 1 ] ans + = 1 # Else we merge left two elements else : i + = 1 arr[i] + = arr[i - 1 ] ans + = 1 return ans # Driver program to test above arr = [ 1 , 4 , 5 , 9 , 1 ] n = len (arr) print ( "Count of minimum operations is " + str (findMinOps(arr, n))) # This code is contributed by Pratik Chhajer |
C#
// C# program to find number of operations // to make an array palindrome using System; class GFG { // Returns minimum number of count operations // required to make arr[] palindrome static int findMinOps( int []arr, int n) { int ans = 0; // Initialize result // Start from two corners for ( int i = 0, j = n - 1; i <= j;) { // If corner elements are same, // problem reduces arr[i+1..j-1] if (arr[i] == arr[j]) { i++; j--; } // If left element is greater, then // we merge right two elements else if (arr[i] > arr[j]) { // need to merge from tail. j--; arr[j] += arr[j + 1] ; ans++; } // Else we merge left two elements else { i++; arr[i] += arr[i-1]; ans++; } } return ans; } // Driver Code public static void Main() { int []arr = new int []{1, 4, 5, 9, 1} ; Console.Write( "Count of minimum operations is " + findMinOps(arr, arr.Length)); } } // This code is contributed by nitin mittal |
PHP
<?php // PHP program to find number // of operations to make an // array palindrome // Returns minimum number of // count operations required // to make arr[] palindrome function findMinOps( $arr , $n ) { // Initialize result $ans = 1; // Start from two corners for ( $i = 0, $j = $n - 1; $i <= $j :winking_face: { // If corner elements are same, // problem reduces arr[i+1..j-1] if ( $arr [ $i ] == $arr [ $j ]) { $i ++; $j --; } // If left element is greater, then // we merge right two elements else if ( $arr [ $i ] > $arr [ $j ]) { // need to merge from tail. $j --; $arr [ $j ] += $arr [ $j + 1] ; $ans ++; } // Else we merge // left two elements else { $i ++; $arr [ $i ] += $arr [ $i - 1]; $ans ++; } } return $ans ; } // Driver Code $arr [] = array (1, 4, 5, 9, 1); $n = sizeof( $arr ); echo "Count of minimum operations is " , findMinOps( $arr , $n ) ; // This code is contributed by nitin mittal. ?> |
Javascript
<script> // JavaScript program to find number of operations // to make an array palindrome // Returns minimum number of count operations // required to make arr[] palindrome function findMinOps(arr, n) { let ans = 0; // Initialize result // Start from two corners for (let i=0,j=n-1; i<=j;) { // If corner elements are same, // problem reduces arr[i+1..j-1] if (arr[i] == arr[j]) { i++; j--; } // If left element is greater, then // we merge right two elements else if (arr[i] > arr[j]) { // need to merge from tail. j--; arr[j] += arr[j+1] ; ans++; } // Else we merge left two elements else { i++; arr[i] += arr[i-1]; ans++; } } return ans; } // Driver Code let arr = [1, 4, 5, 9, 1]; document.write( "Count of minimum operations is " + findMinOps(arr, arr.length)); </script> |
输出：
Count of minimum operations is 1
给定程序的时间复杂度为：O（n）
本文由 杰恩先生 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
