Hiitdromes

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

vector<vector<int>> dp;
string s;
int cost(int a, int b)
{
    if (a > b)
    {
        return 0;
    }
    bool aIs = s[a] == 'H' || s[a] == 'I' || s[a] == 'T';
    bool bIs = s[b] == 'H' || s[b] == 'I' || s[b] == 'T';
    if (a == b)
        return !aIs;
    if (dp[a][b] != INT_MAX)
        return dp[a][b];

    int res = INT_MAX;
    res = min(res, cost(a, b-1)+1);
    res = min(res, cost(a+1, b)+1);



    res = min(res, cost(a+1, b-1)+2);
    if (aIs || bIs)
    {
        res = min(res, cost(a+1, b-1)+1);
        if (s[a] == s[b])
            res = min(res, cost(a+1, b-1));
    }

    dp[a][b] = res;
    return res;
}

signed main() {
    int n;
    cin >> n;
    dp = vector<vector<int>>(n, vector<int>(n, INT_MAX));
    cin >> s;
    cout << cost(0, s.size()-1);
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED