Chương trình tìm số hoạt động cần thiết để xóa danh sách con palindromic trong C ++

Giả sử chúng ta có một danh sách các số được gọi là nums. Bây giờ chúng ta hãy xem xét một hoạt động mà chúng ta xóa một số danh sách phụ là một palindrome. Chúng tôi phải tìm số lượng thao tác tối thiểu cần thiết để danh sách trống.

Vì vậy, nếu đầu vào giống như nums =[6, 2, 4, 4, 2, 10, 6], thì đầu ra sẽ là 2, vì chúng ta có thể loại bỏ danh sách con [2, 4, 4, 2] trước rồi danh sách giống như [6, 10, 6] đây cũng là một palindrome, vì vậy hãy xóa nó để làm cho danh sách trống.

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

• Xác định một mảng dp có kích thước:105 x 105.

• Xác định một hàm dfs (), điều này sẽ lấy i, j, một mảng v,

• ret:=inf

• nếu tôi> j, thì -

  • trả về 0

• nếu tôi giống với j, thì -

  • trả lại 1

• nếu j - tôi giống với 1, thì -

  • return (nếu v [i] giống v [j] thì 1, nếu không thì 2)

• nếu i + 1 <=j và v [i] giống v [i + 1] thì -

  • ret:=1 + dfs (i + 2, j, v)

• nếu dp [i, j] không bằng -1 thì -

  • trả về dp [i, j]

• ret:=tối thiểu của (ret, 1 + (tối thiểu của (dfs (i + 1, j, v) và dfs (i, j - 1, v)))

• nếu v [i] giống v [j] thì -

  • ret:=tối thiểu ret và dfs (i + 1, j - 1, v)

• để khởi tạo k:=i + 2, khi k

  • nếu v [i] giống với v [k], thì &minnus;

    • ret:=tối thiểu ret và dfs ((i + 1, k - 1, v) + dfs (k + 1, j, v))

• return dp [i, j] =ret

• Từ phương thức chính, hãy làm như sau -

• điền dp với -1

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

• trả về dfs ​​(0, n - 1, nums)

Ví dụ

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

#include <bits/stdc++.h>
using namespace std;
int dp[105][105];
int dfs(int i,int j, vector <int>& v){
   int ret= INT_MAX;
   if(i > j)
      return 0;
   if(i == j)
      return 1;
   if(j - i == 1){
      return v[i] == v[j] ? 1 : 2;
   }
   if(i + 1 <= j && v[i] == v[i + 1]){
      ret = 1 + dfs(i + 2, j, v);
   }
   if(dp[i][j] != -1) return dp[i][j];
      ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
   if(v[i] == v[j]){
      ret = min(ret, dfs(i + 1, j - 1, v));
   }
   for(int k = i + 2; k < j; k++){
      if(v[i] == v[k]){
         ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
      }
   }
   return dp[i][j] = ret;
}
int solve(vector<int>& nums) {
   memset(dp , -1, sizeof dp);
   int n = nums.size();
   return dfs(0, n - 1, nums);
}
int main(){
   vector<int> v = {6, 2, 4, 4, 2, 10, 6};
   cout << solve(v);
}

Đầu vào

{6, 2, 4, 4, 2, 10, 6}

Đầu ra

2