Description

给定一个字符串\(s\),对其进行切割使得每个子串都是回文串。求最小切割次数。

Constraints

\(1 \le \mid s \mid \le 2000\)

Solution

很显然,先用DP记录任意区间是否回文串,然后再次DP求最小切割次数。

这里想记录的是一些简单的技巧。

确认回文串时使用true表示空区间和交错的区间,会省下很多判断步骤。但这要求外部调用时需要注意区间范围,以及无法直接使用记录后的表。

和以往的题解一样,使用int数组而非bool数组,这样可以用负数判断是否未遍历,以省下\(vis\)表和打标记操作。

Code

class Solution {
public:
    int minCut(string s) {
        int is[2005][2005];
        memset(is, -1, sizeof is);
        auto DP = [&](auto &&DP, int l, int r) -> int {
            if(l >= r) return true;
            if(~is[l][r]) return is[l][r];
            return is[l][r] = s[l] == s[r] && DP(DP, l+1, r-1);
        };
        int rec[2005];
        for(int i = 0; i < s.size(); ++i) {
            rec[i] = DP(DP, 0, i) ? 1 : i+1;
            if(rec[i] == 1) continue;
            for(int j = 0; j < i; ++j) {
                if(DP(DP, j+1, i)) {
                    rec[i] = min(rec[i], rec[j] + 1);
                }
            }
        }
        return rec[s.size()-1] - 1;
    }
};

LeetCode-132 Palindrome Partitioning II