fork(1) download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3.  
  4. using namespace std;
  5.  
  6. char input_str[510];
  7. int dp[510][510];
  8.  
  9. int dp_solve(int left, int right) {
  10.  
  11.     if (left >= right)
  12.         return 1;
  13.  
  14.     if (dp[left][right])
  15.         return dp[left][right];
  16.  
  17.     int ans = right - left + 1;
  18.     if (input_str[left] == input_str[right])
  19.         ans = min(ans, dp_solve(left + 1, right - 1));
  20.  
  21.     for (int i = left; i < right; i++)
  22.         ans = min(ans, dp_solve(left, i) + dp_solve(i + 1, right));
  23.  
  24.     dp[left][right] = ans;
  25.  
  26.     return ans;
  27. }
  28. int main() {
  29.  
  30.     cin>>input_str;
  31.  
  32.     int str_length=strlen(input_str);
  33.  
  34.     cout<<dp_solve(0, str_length-1)<<endl;
  35.  
  36.     return 0;
  37. }
  38.  
Success #stdin #stdout 0s 17080KB
comments (?)
stdin
copy 
abbxcdca
stdout
copy 
3
https://ideone.com/mUnovg
language:
C++14 (gcc 8.3)
created:
7 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!