Fshl0

Space Jazz

May 23rd, 2021
573
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 500 + 9;
  6.  
  7. int rangeDP[N][N];
  8. string s;
  9.  
  10. int main () {
  11.     string s;
  12.     cin >> s;
  13.     int n = s.length();
  14.     s = '#' + s;
  15.     for (int i = 1; i <= n; i++)
  16.         rangeDP[i][i] = 1;
  17.     for (int len = 2; len <= n; len++) {
  18.         for (int i = 1; i + len - 1 <= n; i++) {
  19.             rangeDP[i][i + len - 1] = rangeDP[i][i + len - 2] + 1;
  20.             for (int k = i; k < i + len - 1; k++)
  21.                 if (s[i + len - 1] == s[k])
  22.                     rangeDP[i][i + len - 1] = min (rangeDP[i][i + len - 1], rangeDP[i][k - 1] + rangeDP[k + 1][i + len - 2]);
  23.         }
  24.     }
  25.     cout << rangeDP[1][n] << "\n";
  26.     return 0;
  27. }
  28.  
RAW Paste Data