Phân vùng Palindrome III trong C ++

Giả sử chúng ta có một chuỗi s chứa các chữ cái thường và một số nguyên k. Chúng tôi phải duy trì một số tài sản. Đây là -

• Đầu tiên, chúng ta phải thay đổi một số ký tự (nếu cần) của s thành các chữ cái tiếng Anh viết thường khác.
• Sau đó chia chuỗi s thành k chuỗi con sao cho mỗi chuỗi con là một palindrome.

Chúng tôi phải tìm số ký tự tối thiểu mà chúng tôi cần thay đổi để chia chuỗi.

Vì vậy, nếu chuỗi giống như “ababbc” và k =2, thì câu trả lời sẽ là 1, vì chúng ta phải thay đổi một ký tự để chia chuỗi này thành hai chuỗi palindrome. Vì vậy, nếu chúng ta thay đổi c thành b, hoặc b cuối cùng thứ hai thành c, thì chúng ta có thể nhận được một palindrome như “bbb” hoặc “cbc” và một palindrome khác là “aba”.

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

• Xác định bản ghi nhớ mảng có kích thước:105 x 105.
• Xác định một hàm giải quyết (), hàm này sẽ nhận s, idx, k, một mảng 2D> dp,
• nếu idx bằng với kích thước của s, thì -
  • trả về khi k bằng 0 thì 0, ngược lại là 1000
• nếu memo [idx] [k] không bằng -1, thì -
  • trả lại thư báo [idx] [k]
• nếu k <=0, thì -
  • thông tin trở lại
• ans:=inf
• để khởi tạo i:=idx, khi tôi
• ans:=tối thiểu ans và dp [idx] [i] + gọi hàm giải quyết (s, i + 1, k - 1, dp)

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;
typedef long long int lli;
class Solution {
public:
   int memo[105][105];
   lli solve(string s, int idx, int k, vector < vector <int> > &dp){
      if(idx == s.size()) {
         return k == 0? 0 : 1000;
      }
      if(memo[idx][k] != -1) return memo[idx][k];
      if(k <= 0)return INT_MAX;
      lli ans = INT_MAX;
      for(int i = idx; i < s.size(); i++){
         ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
      }
      return memo[idx][k] = ans;
   }
   int palindromePartition(string s, int k) {
      int n = s.size();
      memset(memo, -1, sizeof(memo));
      vector < vector <int> > dp(n, vector <int>(n));
      for(int l =2; l <= n; l++){
         for(int i = 0, j = l - 1; j <n; j++, i++){
            if(l==2){
               dp[i][j] = !(s[i] == s[j]);
            }else{
               dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
            }
         }
      }
      return solve(s, 0, k, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.palindromePartition("ababbc", 2));
}

Đầu vào

“ababbc”

Đầu ra

1