LeetCode 664. 奇怪的打印机
原题链接
困难
算法
(区间DP) $O(n^3)$
C++ 代码
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
if (!n) return 0;
vector<vector<int>> f(n, vector<int>(n));
for (int i = 0; i < n; ++i) f[i][i] = 1;
for (int len = 1; len < n; ++len) { // 枚举区间长度
for (int i = 0; i + len < n; ++i) { // 枚举起点
int j = i + len;
f[i][j] = len + 1;
for (int k = i + 1; k <= j; ++k) { // k将当前区间分为两部分
int tmp = f[i][k - 1] + f[k][j];
if (s[k - 1] == s[j]) tmp--; // 两区间合并的时候判断区间尾部是否相同
f[i][j] = min(f[i][j], tmp);
}
}
}
return f[0][n - 1];
}
};