As it is said, use the same trick as Remove Boxes, how could I not think it through. The code is as follows, for those who can access the editorial of RemoveBox, I suggest you go for it, it is well explained. For those who cannot, this article is also well written.

https://discuss.leetcode.com/topic/84687/java-top-down-and-bottom-up-dp-solutions

Basically dp[i][j][k] means that the substring from index i to index j, and with a number of k elements with the same char as s[j]. But in RemoveBoxes, we care the max points, so we keep the max intermediate value in dp array, while in our case, we want to keep the least operation, so we keep min value.

Top-Down solution:

class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
int cache[100][100][100] = {0};
return dfs(s, 0, n - 1, 0, cache);
}
int dfs(string s, int left, int right, int k, int cache[100][100][100])
{
if(left > right)
{
return 0;
}
if(cache[left][right][k] != 0)
{
return cache[left][right][k];
}
while(right > 0 && right >= left && s[right] == s[right - 1])
{
--right;
++k;
}
cache[left][right][k] = dfs(s, left, right - 1, 0, cache) + 1;
for(int i = left; i <= right - 1; ++i)
{
if(s[i] == s[right])
{
cache[left][right][k] = min(cache[left][right][k], dfs(s, left, i, k + 1, cache) + dfs(s, i + 1, right - 1, 0, cache));
}
}
return cache[left][right][k];
}
};

Bottom-Up solution:

First, we just translate the Top-Down solution to Bottom-Up solution, also we use a three-dimensional dp array to store the intermediate results, and we got this code.

class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
if(n == 0)
{
return 0;
}
int dp[102][102][102];
for(int i = 0; i < n; ++i)
{
for(int k = 0; k <= 100; ++k)
{
dp[i][i][k] = 1;
}
}
for(int len = 2; len <= n; ++len)
{
for(int left = 0; left + len - 1 < n; ++left)
{
int right = left + len - 1;
for(int k = 0; k <= 100; ++k)
{
dp[left][right][k] = dp[left][right - 1][0] + 1;
for(int m = left; m <= right - 1; ++m)
{
if(s[m] == s[right])
{
dp[left][right][k] = min(dp[left][right][k], dp[left][m][k + 1] + dp[m + 1][right - 1][0]);
}
}
}
}
}
return dp[0][n-1][0];
}
};

Then we found that the 3th dimension info (for dp[i][j][k], which is the k element following s[j] and has the same value as s[j]) can be ignored, so we optimize the three dimensional array to two dimensional arry and got this step, and the time complexity is reduced from O(n^4) to O(n^3).

class Solution {
public:
int strangePrinter(string s) {
int n = s.size();
if(n == 0)
{
return 0;
}
int dp[102][102] = {0};
for(int i = 0; i < n; ++i)
{
dp[i][i] = 1;
}
for(int len = 2; len <= n; ++len)
{
for(int left = 0; left + len - 1 < n; ++left)
{
int right = left + len - 1;
dp[left][right] = dp[left][right - 1] + 1;
for(int m = left; m <= right - 1; ++m)
{
if(s[m] == s[right])
{
dp[left][right] = min(dp[left][right], dp[left][m] + dp[m + 1][right - 1]);
}
}
}
}
return dp[0][n-1];
}
};