题目描述
状态表示:f[i][j]表示从i到j打印需要最少的打印次数。
最坏的情况:f[i][j] = j - i + 1;
状态转移:f[i][j] = min(f(i, k) + f(k + 1, j) - 1)) :如果s[k] == s[j], i <= K < j;
也就是说如果发现在j之前有和j的位置相同的话就可以在最坏的情况下减少一次。
C++ 代码
class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
if (!n) return 0;
vector<vector<int>> f(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < n; i ++) {
f[i][i] = 1; //only print one;
}
for(int j = 1; j < n; j ++) { // j distance between start and end of s;
for (int i = 0; i + j < n; i ++) {
f[i][i + j] = j + 1; // worse case i + j - i + 1;
for (int k = i; k < i + j; k ++) {
int total = f[i][k] + f[k + 1][i + j];
if (s[k] == s[i + j]) {
total --;
}
f[i][i + j] = min(f[i][i + j], total);
}
}
}
return f[0][n - 1];
}
};