Palindrome Partitioning II

https://leetcode.com/problems/palindrome-partitioning-ii/description/

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Thoughts

string做划分，使得每个substring是回文，问最少划分数目。action为找一个元素j使得它到当前元素i组在一起，受限于是否回文，因此用另一个DP求dp[j:i]是否回文。

Code

/*
 * @lc app=leetcode id=132 lang=cpp
 *
 * [132] Palindrome Partitioning II
 */
class Solution {
public:
    vector<vector<bool>> isPalindrome(string s) {
        const int N = s.size();
        vector<vector<bool>> dp(N, vector<bool>(N));
        for (int i = 0; i < N; ++i) dp[i][i] = true;
        for (int i = N; i >= 0; --i) {
            for (int j = i + 1; j < N; ++j) {
                if (s[i] == s[j] && (j == i + 1 || dp[i + 1][j - 1])) dp[i][j] = true; 
            }
        } 
        return dp;
    }

    int minCut(string s) {
         const int N = s.size();
         const auto &palind = isPalindrome(s);
         vector<int> dp(N);
         for (int j = 1; j < N; ++j) {
             if (palind[0][j]) {
                 dp[j] = 0;
                 continue;
             }
             dp[j] = dp[j - 1] + 1;
             for (int i = 0; i < j; ++i) {
                 if (palind[i][j]) dp[j] = min(dp[j], dp[i - 1] + 1); 
             }
         }
         return dp[N - 1]; 
    }
};

Analysis

TC: $O(n^2)$

注意(f[i - 1][j + 1] || j + 1 == i)