1695 c++

Flow

이 문제는 일단, 다른 비슷한 팰린드롬으로부터 dp임을 생각을 하고 풀었다.
그렇다면 top-down으로 해보자

그림과 같이 길이가 1이면 무조건 0이다. 그자체로 팰린드롬이니까
길이가 2이면 숫자가 다르면 무조건 1이다. 하나를 추가해야하니까

그러핟면 3부터는 어떻게 될까
1,2,3이 다르면 두가지 경우가 있다.
맨처음숫자 1을 추가해서 1,2,3,1인경우
맨 끝숫자 3을 추가해서 3,1,2,3인경우
그렇다면 어떤걸 추가해야할까?

만약에 1,2,3이아니라
1,2,2라고 생각해보자,
1,2,2,1은 하나만 추가하면되는데
2를 앞에다 추가하려면 2,2,1,2,2로 2를 2개추가해야한다.

여기서 부터
1,2의 팬린드롬만드는데 필요한 숫자와
2,2를 팬린드롬 만드는데 숫자를 비교하면된다.

1,2의 팬린드롬 만드는데 필요한 숫자가 1이니까 1+1
2,2는 이미 팬린드롬 0이니까 0+1로 정답 1부터3까지는 1이된다.

이식이
min(check(start+1,end),check(start,end-1))이 된다.

만약에 같으면 어떻게 될까?
1,2,3,1이런식으로 말이다. 그러면 2,3의 팬린드로 만드는 숫자를 알면된다.
dp[1][4] = check(start+1,end-1)이다.

또한 dp느낌이 나는게 위 그림 삼각형처럼 재귀를 부르더라도 이미 최적의 값을 찾으면 다시 호출하지 않도록 -1이면 호출 아니면 반환 이런식으로 처리했다.

#include <iostream>
#include <algorithm>
using namespace std;

int N;
int arr[5001];
int dp[5001][5001];

void init() {
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }

    // dp 초기화
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dp[i][j] = -1;
        }
    }

    // 길이 1
    for (int i = 1; i <= N; i++) dp[i][i] = 0;

    // 길이 2
    for (int i = 1; i < N; i++) {
        dp[i][i + 1] = (arr[i] == arr[i + 1] ? 0 : 1);
    }
}

int check(int start, int end) {
    if (dp[start][end] != -1) return dp[start][end];

    if (arr[start] == arr[end]) {
        dp[start][end] = check(start + 1, end - 1);
    } else {
        dp[start][end] = min(check(start + 1, end), check(start, end - 1)) + 1;
    }

    return dp[start][end];
}

void solve() {
    check(1, N); // 실제 계산은 여기서 다 된다
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    init();
    solve();
    cout << dp[1][N] << "\n";
    return 0;
}