Loại bỏ Palindrome trên C ++

Giả sử chúng ta có một mảng số nguyên được gọi là arr, bây giờ trong một lần di chuyển, chúng ta có thể chọn một mảng con palindromic từ chỉ mục i đến j trong đó i <=j và xóa mảng con đó khỏi mảng đã cho. Chúng ta phải lưu ý rằng sau khi xóa một mảng con, các phần tử ở bên trái và bên phải của mảng con đó sẽ di chuyển để lấp đầy khoảng trống do việc xóa bỏ. Chúng ta phải tìm số lần di chuyển tối thiểu cần thiết để xóa tất cả các số khỏi mảng.

Vì vậy, nếu đầu vào là arr =[1,3,4,1,5], thì đầu ra sẽ là 3, vì chúng ta có thể loại bỏ trong trình tự này, loại bỏ [4] rồi loại bỏ [1,3,1] sau đó loại bỏ [5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của arr

• Xác định một dp mảng 2D có kích thước (n + 1) x (n + 1)

• để khởi tạo l:=1, khi l <=n, cập nhật (tăng l lên 1), thực hiện -

  • để khởi tạo i:=0, j:=l - 1, khi j

    • nếu l giống với 1, thì -

      • dp [i, j]:=1

    • Nếu không

      • dp [i, j]:=1 + dp [i + 1, j]

      • nếu i + 1

        • dp [i, j]:=tối thiểu của dp [i, j] và 1 + dp [i + 2, j]

      • để khởi tạo k:=i + 2, khi k <=j, cập nhật (tăng k lên 1), thực hiện -

        • nếu arr [i] giống arr [k] thì -

          • dp [i, j]:=tối thiểu của dp [i, j] và dp [i + 1, k - 1] + dp [k + 1, j]

• trả về dp [0, n - 1]

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   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(){
   Solution ob;
   vector<int> v = {1,2};
   cout << (ob.minimumMoves(v));
}

Đầu vào

[1,2]

Đầu ra

2