fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int t[100][100];
  4. bool pailndrome(string s,int i,int j){
  5. 	for(int k=0;k<(j-i+1)/2;k++){
  6. 		if(s[k+i]!=s[j-k]){
  7. 			return false;
  8. 		}
  9. 	}
  10. 	return true;
  11.  
  12. }
  13.  
  14. int solve(string s,int i,int j){
  15. 	if(i>=j){
  16. 		return 0;
  17. 	}
  18. 	if(pailndrome(s,i,j)){
  19. 		return 0;
  20. 	}
  21. 	if(t[i][j]!=-1){
  22. 		return t[i][j];
  23. 	}
  24. 	int mn=INT_MAX;
  25. 	for(int k=i;k<j;k++){
  26.  
  27.  
  28.  
  29. 		int temp=1+solve(s,i,k)+solve(s,k+1,j);
  30. 		if(temp<mn){
  31. 			mn=temp;
  32. 		}
  33. 		return t[i][j]=mn;
  34.  
  35. 	}
  36.  
  37. }
  38.  
  39.  
  40. int main() {
  41. 	string s="stoot";
  42. 	int i=0;
  43. 	int j=s.size()-1;
  44. 	memset(t,-1,sizeof(t));
  45. 	cout<<solve(s,i,j);
  46. 	return 0;
  47. }
Success #stdin #stdout 0s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/OVju6t
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!