IOI '00 P1 - Palindrome (2)

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

using namespace std;

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