Hiitdromes

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int MAX_N = 1e3 + 23;
const int INF   = 1e9;

int dp[MAX_N][MAX_N];
string s;

int calc_dp(int l, int r)
{
    if (dp[l][r] != INF)
        return dp[l][r];

    if (l > r)
    {
        dp[l][r] = INF;
        return dp[l][r];
    }

    if (l == r)
    {
        dp[l][r] = 0;
        return dp[l][r];
    }

    if ((l + 1) == r)
    {
        dp[l][r] = (s[l] != s[r]);
        return dp[l][r];
    }

    dp[l][r] = INF;

    // Add a new symbol that equals to s[l]
    if (l + 1 <= r)
        dp[l][r] = min(dp[l][r], calc_dp(l + 1, r) + 1);

    // Delete symbol s[r]
    if (l <= r - 1)
        dp[l][r] = min(dp[l][r], calc_dp(l, r - 1) + 1);

    // Replace symbol s[r] by symbol that equals to s[l]
    if ((l + 1) <= (r - 1))
        dp[l][r] = min(dp[l][r], calc_dp(l + 1, r - 1) + (s[l] != s[r]));

    assert(dp[l][r] != INF);

    return dp[l][r];
}

int main()
{
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;

    cin >> s;

    for (int i = 0; i < MAX_N; i++)
        for (int j = 0; j < MAX_N; j++)
            dp[i][j] = INF;

    int answer = calc_dp(0, n - 1);
    cout << answer << '\n';

    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: ACCEPTED

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED