spoj-AIBOHPHOBIA

                                  SPOJ- AIBOHPHOBIA

hello friends this is a solution of aibohphobia spoj link this queston is baisically on "dp" dynamic programming..

now how to solve this problem first of all :

suppose the string is "fftt"

now doing a bottom up approach:

making two dimensional array: first array will store for odd length substring second array even                                                              length string array ....... 

now we now single character is itself palindrome right!!

so

dp[0][]:                    0     |    0     |     0     |     0                 [dp[0 or 1][1] is the require answer think!!!]

                               1-1       2-2      3-3        4-4

dp[1][]                     0     |     2    |     0                         [2 more character will make "ft" pallindrome]

                              1-2        2-3      3-4

now starting the loop....

l: length of the substring

i: starting index

j: ending index

now :                                          

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<bits/stdc++.h> int max(int a,int b) { return(a>b)?a:b; } int min(int a,int b) { return(a<b)?a:b; } int main() { int n,t,k=0; scanf("%d",&t); char s[6105]; while(t--) { k=0; int dp[2][6105]={0}; scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<n;i++) dp[1][i]=(s[i]!=s[i+1])?2:0; k=1; for(int l=2;l<n;l++) { k=(l&1)?1:0;//0 : single "1" and 1 is double "11" for(int i=1;i<n-l+1;i++) { int j=i+l; int x=0; if(s[i]==s[j]) dp[k][i]=dp[k][i+1]; else dp[k][i]=2+dp[k][i+1]; x=min(1+dp[!k][i+1],1+dp[!k][i]); dp[k][i]=min(dp[k][i],x); } } printf("%d\n",dp[k][1]); } return 0; }

hope this tutorial was helpful and comment any suggestion... thank you
have a nice day.... :)