Palindrome Partition 구분

// dp[i] = min{ dp[i - k] if (s[k] == s[i]) && (s[k+1..i-1] is palindrome) }, k = 0,1,2...i. dp[i]           

//.h

#include 

class PalindromePartition {
public:
    static void test();

    static int minCut(std::string &s);

    static bool isPalindrome(const std::string &s);

};

//.cpp
//
// Created on 3/14/18.
//

#include 
#include 
#include "PalindromePartition.h"

using namespace std;

// dp[i] = min{dp[i - k] if (s[k] == s[i]) && (s[k+1..i-1] is palindrome) }, k = 0,1,2...i. dp[i]           
int PalindromePartition::minCut(std::string &s) {
    const int N = s.size();

    if (isPalindrome(s)) {
        return 0;
    }

    vector> mat(N, vector(N, 0));

    for (int i = 0; i < N; i++) {
        mat[i][i] = 1;
    }

    vector dp(N, 0);
    for (int i = 0; i < N; i++) {
        dp[i] = 0x0fffffff;
        for (int j = 0; j <= i; j++) {
            if ((s[j] == s[i])) {
                if (j + 1 <= i - 1) {
                    if (!mat[j+1][i-1]) {
                        continue;
                    }
                }
                mat[j][i] = 1;
                if (j - 1 >= 0) {
                    dp[i] = min(dp[i], dp[j - 1] + 1);
                } else {
                    dp[i] = 0;
                }
            }
        }

    }
    return dp[N - 1];
}

bool PalindromePartition::isPalindrome(const std::string &s) {
    if (s.size() <= 1) {
        return true;
    }

    const int N = s.size();
    for (int i = 0; i < N / 2; i++) {
        if (s[i] != s[N - i - 1]) {
            return false;
        }
    }
    return true;
}

void PalindromePartition::test() {
    vector vec = {
            "abbab",
            "aab",
            "abccba",
            "abcabc",
            "aaabaaa",
            "aabcaa",
            "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa",
    };
    for (auto &s: vec) {
        cout << minCut(s) << endl;
    }
}