fork(4) download
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. int **answers;
  6. string s;
  7.  
  8. int calculate(int l, int r){
  9. if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.
  10. if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
  11. answers[l][r] = s.size();
  12. if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));
  13. for(int i = l; i < r; ++i){
  14. answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));
  15. }
  16. }
  17. return answers[l][r];
  18. }
  19.  
  20. int main() {
  21. getline(cin, s); //Ввод строки.
  22.  
  23. answers = new int*[s.size()];
  24. for(int i = 0; i < s.size(); ++i){
  25. answers[i] = new int[s.size()];
  26. }
  27. //Заполнение массива начальными значениями.
  28. for(int i = 0; i < s.size(); ++i){
  29. for(int j = 0; j <= s.size(); ++j){
  30. if(i == j) answers[i][j] = 1;
  31. else answers[i][j] = -1;
  32. }
  33. }
  34. //Вывод ответа.
  35. cout<<calculate(0, s.size()-1);
  36. return 0;
  37. }
Success #stdin #stdout 0s 15240KB
stdin
abbac
stdout
1