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;
}
};