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. 		int left,right;
  27. 		if(t[i][k]!=-1){
  28. 			left=t[i][k];
  29. 		}else{
  30. 			left=solve(s,i,k);
  31. 		}
  32.  
  33. 		if(t[k+1][j]!=-1){
  34. 			right=t[k+1][j];
  35. 		}else{
  36. 			right=solve(s,k+1,j);
  37. 		}
  38.  
  39.  
  40. 		int temp=1+left+right;
  41. 		if(temp<mn){
  42. 			mn=temp;
  43. 		}
  44. 		return t[i][j]=mn;
  45.  
  46. 	}
  47.  
  48. }
  49.  
  50.  
  51. int main() {
  52. 	string s="stoot";
  53. 	int i=0;
  54. 	int j=s.size()-1;
  55. 	memset(t,-1,sizeof(t));
  56. 	cout<<solve(s,i,j);
  57. 	return 0;
  58. }
Success #stdin #stdout 0.01s 5484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/urC6ea
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!