Code : Clear the String

#include <bits/stdc++.h>
using namespace std;

const int inf = 1e6;

int solve(string &str) {
    int n = str.size();

    // dp[i][j] represents the minimum operations to reduce substring str[i..j]
    // to an empty string.
    vector<vector<int>> dp(n, vector<int>(n, inf));
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            // Single element : Only 1 move needed.
            if (i == j) {
                dp[i][j] = 1;
                continue;
            }

            // We have 2 choices:
            // 1. The first element of the substring is deleted alone.
            int delete_alone = 1 + dp[i + 1][j];

            // 2. The first element of the substring is merged with another
            // element at index k.
            int merge = inf;
            for (int k = i + 1; k <= j; k++) {
                if (str[i] == str[k]) {
                    // Notice that the left contribution would be initialised
                    // with 0 and not infinity. Consider "aab".
                    int left_contribution = 0;
                    if (k - 1 >= i + 1) {
                        left_contribution = dp[i + 1][k - 1];
                    }
                    int right_contribution = dp[k][j];
                    merge = min(merge, left_contribution + right_contribution);
                }
            }

            dp[i][j] = min(delete_alone, merge);
        }
    }

    return dp[0][n - 1];
}

int main() {
    int n;
    cin >> n;

    string str;
    cin >> str;

    int res = solve(str);
    cout << res << endl;
}