IOI '00 P1 - Palindrome

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n; string s;
    cin >> n >> s;
    vector<vector<short>> dp(n);
    // dp[i][j] = min characters to add to make s[i],...,s[i+j-1] a palindrome
    for (int i = 0; i < n; ++i) dp[i].resize(n-i+1);
    for (int sz = 2; sz <= n; ++sz) {
        for (int left = 0; left+sz <= n; ++left) {
            int right = left+sz-1;
            if (s[left] == s[right]) dp[left][sz] = dp[left+1][sz-2];
            else dp[left][sz] = min(dp[left+1][sz-1], dp[left][sz-1]) + 1;
        }
    }
    cout << dp[0][n] << endl;
    return 0;
}