132. 分割回文串 II
怎么用确定
f[i][j]区间是否是回文串
左端点从最右往左遍历，固定左端点，右端点从左往右
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
我注释里写的这个是不行的
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// f[i][j] = f[i + 1][j - 1] && s[i] == s[j];
// }
// }
必须从小区间到大区间，这样才能保证计算f[i][j]的时候f[i+1][j-1]被算过了
我这种写法上来就是算了最长的区间i=0~j=n-1，实际上中间f[i+1][j-1]是没有被计算过的
固定右端点（从左往右），左端点从右往左也是可以的
for (int j = 1; j < n; j++) {
for (int i = j - 1; i >= 0; i--) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
class Solution {
public:
int minCut(string s) {
int n = s.size();
int f[n][n];
memset(f, true, sizeof f);
// for (int i = 0; i < n; i++) {
// for (int j = i + 1; j < n; j++) {
// f[i][j] = f[i + 1][j - 1] && s[i] == s[j];
// }
// }
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
}
}
int dp[n];
memset(dp, 0x3f, sizeof dp);
for (int i = 0; i < n; i++) {
if (f[0][i]) dp[i] = 0;
for (int j = 0; j < i; j++) {
if (f[j + 1][i])dp[i] = min(dp[i], dp[j] + 1);
}
}
return dp[n - 1];
}
};
