1695 팰린드롬 만들기

#include <stdio.h>
 
int arr[5005] = { 0 };
int dp[5005][5005] = { 0 };
 
int div(int l, int r) {
    if (dp[l][r] != 0) {
        return dp[l][r];
    }
 
    if (l == r) {
        dp[l][r] = 0;
        
        return 0;
    }
    else if (l + 1 == r) {
        if (arr[l] != arr[r])
            dp[l][r] = 1;
        else
            dp[l][r] = 0;
        
        return dp[l][r];
    }
 
    if (arr[l] == arr[r]) {
        dp[l][r] = div(l + 1, r - 1);
        return dp[l][r];
    }
    else {
        int val1 = div(l + 1, r);
        int val2 = div(l, r - 1);
 
        if (val1 < val2) {
            dp[l][r] = val1 + 1;
 
            return dp[l][r];            
        }
        else {
            dp[l][r] = val2 + 1;
 
            return dp[l][r];
        }
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
    }
 
    int rst = div(1, n);
    printf("%d", rst);
}