Palindrom Bölmə birdir DP problemi. Bu problemdə, bölmənin hər alt sətirinin palindrom olması üçün S. bölməsi verilmişdir. S-nin palindromla bölünməsi üçün lazım olan minimum kəsikləri yazdırmalıyıq.
Mündəricat
Giriş Formatı
Yalnız S sətri olan bir sətir.
Çıxış formatı
S-nin palindromlu bölüşdürülməsi üçün lazım olan minimum kəsik olan tək tam ədədi çap edin.
Məhdudiyyətlər
- 1 <= | s | <= 1000.
Example Input: abcdefedc
Example Output: 2
Palindrom Bölmə üçün İzahat
Burada 3 kəsikdən istifadə edərək ipi 2 alt telə böldük. Substrings "a", "b", "cdefedc" dir. Burada bir alt sətrin palindrom olub olmadığını izah edən məlumatların saxlanması üçün 2B matrisdən istifadə edirik. DP [i] [j] 1-dirsə, s (i, j) alt sətri başqa bir palindromdur DP [i] [j] = 0 deməkdir. İndi minimum kəsilmələrin sayı üçün əvvəlki kəsim haqqında məlumatları [0-i] -dən saxlayan bir sıra lazımdır.
DP [0] [1] 1-dirsə, [i] = 0-ı başqa şəkildə kəsir, j + 1-dən i-yə alt sətrin palindrom olduğunu və [j] +1 kəsiklərinin minimum 0 <= j olduğu mümkün olduğunu yoxlayın.
Bundan sonra istirahət alt telləri üçün tapdığımız minimum kəsiklərdən istifadə edərək minimum kəsikləri 0-dan i-yə qədər yeniləməyimiz lazımdır.
Palindrom Bölmə üçün Alqoritm
Algorithm:
Step:1 Set dp[n][n]=0.
Step:2 Set dp[i][i]=1 for all i where 0<=i<n.This is for all substrings of length 1 are palindrome.
Step:3 For all values of i where 0<=i<n-1, we check if s[i]=s[i+1] then dp[i][i+1]=1. This is for all substrings of length 2 are palindrome.
Step:4 For rest of the other length substring:
for i in range 3 to n:
for j in range 0 to n-i:
last=j+i-1.
if s[j]=s[last] then:
if dp[j+1][last-1] then:
dp[j][last]=1;
Step:5 Count the minimum cuts required. Make a array cuts of size n and set all its value as 1e9.
for i in range 0 to n-1:
set calc as 1e9.
if dp[0][i] is 1 then:
cuts[i]=0;
else:
for j in range 0 to i-1:
if dp[j+1][i]=1 and calc greater than (cuts[j]+1) then:
set calc=cuts[j]+1.
set cuts[i]=calc;
Step:6 Print the value of cuts[n-1].
Palindrom Bölmə üçün tətbiqetmə
/*C++ Implementation of Palindrome Partitioning using DP approch*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*input string*/
string s;
cin>>s;
int n=s.length();
int dp[n+1][n+1];
/*set 0 to all cell of dp matrix.*/
memset(dp,0,sizeof(dp));
/*for all 1 length substrings which are palindrome.*/
for(int i=0;i<n;i++)
{
dp[i][i]=1;
}
/*for all 2 length substrings which are palindrome.*/
for(int i=0;i<n-1;i++)
{
if(s[i]==s[i+1])
{
dp[i][i+1]=1;
}
}
/*for all substrings greater than length 2 which are palindrome.*/
for(int i=3;i<=n;i++)
{
for(int j=0;j<n-i+1;j++)
{
int last=j+i-1;
/*first and last char must be the same.*/
if(s[j]==s[last])
{
/*substring s[i+1 to j-1] must be palindrome.*/
if(dp[j+1][last-1])
{
dp[j][last]=1;
}
}
}
}
int cuts[n];
/*set maximum value(1e9) to each cell of cuts array*/
memset(cuts,1e9,sizeof(cuts));
/*calculating minimum cuts*/
for(int i=0;i<n;i++)
{
int calc=1e9;
/*if substring from 0 to i is palindrome*/
if(dp[0][i])
{
cuts[i]=0;
}
else/*others casec*/
{
/*check for all index less than i to get the minimum cuts for j to i*/
for(int j=0;j<i;j++)
{
/*if substring from j+1 to i is a palindrome */
if((dp[j+1][i])&&calc>cuts[j]+1)
{
calc=cuts[j]+1;
}
}
cuts[i]=calc;
}
}
/*print the minimum cut required value*/
cout<<cuts[n-1]<<endl;
return 0;
}
ssadafudedufadddd
3
Zamanın mürəkkəbliyi
O (N * N) burada N simli uzunluqdur. Dp matrisindəki dəyərləri yenilədikdə istifadə etdiyimiz döngü üçün iç içə yerləşdiyi bütün mümkün cütlükləri ziyarət etməliyik.
Kosmik Mürəkkəblik
O (N * N) burada N simli uzunluqdur. Bir alt sətrin palindrom olub olmadığını yoxlamaq üçün 2 dəyərlərini saxlamaq üçün N * N sıralı 0,1d DP matrisini yaradırıq.
