[BOJ/백준][Gold3] 5502 : 팰린드롬 (C++)

https://www.acmicpc.net/problem/5502

 

[난이도] Gold3
[유형] DP

[풀이]
DP[l][r] : index l부터 index r까지의 문자열을 팰린드롬으로 만들기 위해 삽입해야할 문자의 최수 갯수

점화식 : DP[l][r] = min(
DP[l+1][r]+1, s[l]과 같은 문자를 r+1에 삽입할 때
DP[l][r-1]+1, s[r]과 같은 문자를 l-1에 삽입할 때
DP[l+1][r-1]+1 (if s[l]==s[r]인 경우)
)

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/5502.cpp

 

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N,dp[5001][5001],inf=9e8;
string s;
int sol(int l,int r){
    if(l>=r) return 0;
    int& ret = dp[l][r];
    if(ret!=-1) return ret;
    ret = inf;
    if(s[l]==s[r]) ret = min(ret,sol(l+1,r-1));
    ret = min(ret,1+sol(l+1,r));
    ret = min(ret,1+sol(l,r-1));
    return ret;
}
int main(){
    cin >> N >> s;
    memset(dp,-1,sizeof(dp));
    cout << sol(0,N-1);
}