partition_palindrome.cc

class Solution {
public:
    int minCut(string s) {
        vector<vector<int>> p_map;
        vector<int> c_map;
        for (int i = 0; i < s.size(); i++) {
            p_map.push_back(vector<int>(s.size(), -1));
            c_map.push_back(-1);
        }
        for (int i = 0; i < s.size(); i++) {
            p_map[i][i] = 1;
        }
        return minCut(s, p_map, c_map, 0);
    }
    
    bool is_palindrome(string &s, vector<vector<int>> &p_map, int i, int j) {
        if (j + 1 == i) {
            return true;
        }
        
        if (p_map[i][j] == 0) {
            return false;
        } else if (p_map[i][j] == 1) {
            return true;
        } else {
            if (s[i] == s[j] && is_palindrome(s, p_map, i + 1, j - 1)) {
                p_map[i][j] = 1;
                return true;
            } else {
                p_map[i][j] = 0;
                return false;
            }
        }
    }
    
    int minCut(string &s, vector<vector<int>> &p_map, vector<int> &c_map, int i) {
        if (c_map[i] != -1) {
            return c_map[i];
        }
        int min = INT_MAX;
        if (is_palindrome(s, p_map, i, s.size() - 1)) {
            c_map[i] = 0;
            return 0;
        }
        for (int j = i; j < s.size() - 1; j++) {
            if (is_palindrome(s, p_map, i, j)) {
                int temp = 1 + minCut(s, p_map, c_map, j + 1);
                if (temp < min) {
                    min = temp;
                }
            }
        }
        c_map[i] = min;
        return min;
    }
};