SMMR-109: Magic Spell III

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

string str;
int n;
int main(){

    cin>>str;
    n = str.size();
    int dp[n+1][n+1];

    for(int i=n;i>=0;i--){
        for(int j=n;j>=0;j--){
            if(i==n or j==n) dp[i][j] = 0;
            else if(i != j and str[i] == str[j]) dp[i][j] = 1 + dp[i+1][j+1];
            else if(i+1 <= n and j+1 <= n) dp[i][j] = max(dp[i][j+1], dp[i+1][j]);
            else if(i+1 > n) dp[i][j] = dp[i][j+1];
            else if(j+1 > n) dp[i][j] = dp[i+1][j];
        }
    }

    printf("%d",dp[0][0]);

    return 0;
}