Hiitdromes

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

long long p = 1000000007;

long long power(long long x, long long n) {
  if(n == 0) return (1 % p);
  long long xx = power(x, n/2);
  xx = (xx * xx) % p;
  if(n%2==1) xx = (xx * x) % p;
  return xx;
}

int n;
string s;

int dp[1010][1010];

bool ok(char c) {
  return (c == 'I' || c == 'H' || c == 'T');
}

int memo(int i, int j) {
  if(j-i + 1 == 0) return 0;
  if(j < i) return p;
  if(dp[i][j] != -1) return dp[i][j];
  if(i == j) return !ok(s[i]);
  int ans = min(memo(i+1,j)+1, memo(i,j-1)+1);
  if(ok(s[i]) && s[i] == s[j]) ans = min(ans, memo(i+1,j-1));
  if(ok(s[i])) {
    ans = min(ans, memo(i+1, j) + 1);
    ans = min(ans, memo(i+1, j-1) + 1);
  }
  if(ok(s[j])) {
    ans = min(ans, memo(i, j-1) + 1);
    ans = min(ans, memo(i+1, j-1) + 1);
  }
  ans = min(ans, memo(i+1, j-1) + 2);
  return dp[i][j] = ans;
}

int main() {

  cin >> n >> s;
  memset(dp, -1, sizeof dp);
  cout << memo(0, n-1) << endl;
  
  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