Dear reader, in this tutorial today, learn how to find the minimum number of moves required to extract all numbers from an array in C ++?

An integer array called arr, now in a move we can select a palindromic subarray from the index i to j from where i <= j occurs and remove that subarray from the given array. We need to keep in mind that after removing a subray, move the elements to the left and the gap to the right of that subray to fill. We have to find the minimum number of moves required to extract all numbers from the array.

Therefore, if the input is like arr = [1,3,4,1,5], the output will be 3, as we can extract in this order, remove [4], then [1,3,1 ] Remove remove [5].

#include <bits/stdc++.h>
using namespace std;
class program{
   public:
   int minimumMoves(vector<int>& arr) {
      int n = arr.size();
      vector<vector<int> > dp(n + 1, vector<int>(n + 1));
      for (int l = 1; l <= n; l++) {
         for (int i = 0, j = l - 1; j < n; i++, j++) {
            if (l == 1) {
               dp[i][j] = 1;
            } else {
               dp[i][j] = 1 + dp[i + 1][j];
               if (i + 1 < n && arr[i] == arr[i + 1])
               dp[i][j] = min(dp[i][j], 1 + dp[i + 2][j]);
               for (int k = i + 2; k <= j; k++) {
                  if (arr[i] == arr[k]) {
                     dp[i][j] = min(dp[i][j], dp[i + 1][k - 1] + dp[k + 1][j]);
                  }
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   public ob;
   vector<int> v = {1,2};
   cout << (ob.minimumMoves(v));
}

Result

2