Hiitdromes

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define X real()
#define Y imag()

int dp[1010][1010];

int check(char c1, char c2) {
    if (c1=='H' || c1=='I' || c1=='T') {
        if (c2==c1) return 0;
        else return 1;
    }
    if (c2=='H' || c2=='I' || c2=='T') return 1;
    return 2;
}

int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    for (int i=0;i<n;i++) {
        dp[i][i]=0;
        if (s[i]=='H' || s[i]=='I' || s[i]=='T') dp[i][i+1]=0;
        else dp[i][i+1]=1;
    }
    for (int i=n-2;i>=0;i--) {
        for (int j=i+2;j<=n;j++) {
            dp[i][j]=dp[i+1][j]+1;
            dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
            dp[i][j]=min(dp[i][j],dp[i+1][j-1]+check(s[i],s[j-1]));
        }
    }
    cout<<dp[0][n]<<"\n";
}

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