백준 1509 팰린드롬 분할

우선 dp를 돌기 전에 isPal 이차원 배열을 만들어 놓고, L번째 index와 R번째 index 사이의 string이 palindrome이 맞으면 1, 아니면 0을 저장한다. 

 

그리고 dp[index] = index에서 시작하여 string 끝까지 만들 수 있는 최소 팰린드롬 분할 갯수라고 정의하자.

즉 우리가 알고싶은 답은 dp[0]의 값이다.

 

i를 index~string 끝까지 돌렸을 떄 isPal[index][i]가 1이라면, index~i까지는 palindrome이라고 할 수 있고, 그 뒤에 남은 string에 대해 최솟값을 구해주는 식으로 짜면 된다.

 

string s;
vector<int> dp;
vector<vector<int>> isPal;
int dfs(int index) {
    if (index == s.length()) return 0;
    int& ret = dp[index];
    if (ret != -1) return ret;
    ret = INF;
    rep(i, index, s.length()) {
        if (isPal[index][i] == 1) {
            ret = min(ret, 1 + dfs(i + 1));
        }
    }
    return ret;
 }
bool isPall(string ss) {
    rep(i, 0, ss.length()) {
        if (ss[i] != ss[ss.length() - 1 - i]) return 0;
    }
    return 1;
}
 
int main() {
    cin >> s;
    isPal = VVI(s.length(), VI(s.length()));
    dp = vector<int>(s.length(), -1);
    rep(i, 0, s.length()) {
        rep(j, i, s.length()) {
            string ss = s.substr(i, j - i + 1);
            if (isPall(ss)) isPal[i][j] = 1;
        }
    }
    
    cout << dfs(0);
    return 0;
}