Space Jazz

#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 9;

int rangeDP[N][N];
string s;

int main () {
    string s;
    cin >> s;
    int n = s.length();
    s = '#' + s;
    for (int i = 1; i <= n; i++)
        rangeDP[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            rangeDP[i][i + len - 1] = rangeDP[i][i + len - 2] + 1;
            for (int k = i; k < i + len - 1; k++)
                if (s[i + len - 1] == s[k])
                    rangeDP[i][i + len - 1] = min (rangeDP[i][i + len - 1], rangeDP[i][k - 1] + rangeDP[k + 1][i + len - 2]);
        }
    }
    cout << rangeDP[1][n] << "\n";
    return 0;
}